//===--- Verifier.cpp - Verification of Swift PIL Code --------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "pil-verifier"

#include "polarphp/ast/AstContext.h"
#include "polarphp/ast/AnyFunctionRef.h"
#include "polarphp/ast/Decl.h"
#include "polarphp/ast/ExistentialLayout.h"
#include "polarphp/ast/GenericEnvironment.h"
#include "polarphp/ast/Module.h"
#include "polarphp/ast/ParameterList.h"
#include "polarphp/ast/InterfaceConformance.h"
#include "polarphp/ast/Types.h"
#include "polarphp/basic/Range.h"
#include "polarphp/clangimporter/ClangModule.h"
#include "polarphp/pil/lang/ApplySite.h"
#include "polarphp/pil/lang/BasicBlockUtils.h"
#include "polarphp/pil/lang/DebugUtils.h"
#include "polarphp/pil/lang/Dominance.h"
#include "polarphp/pil/lang/DynamicCasts.h"
#include "polarphp/pil/lang/MemAccessUtils.h"
#include "polarphp/pil/lang/MemoryLifetime.h"
#include "polarphp/pil/lang/PostOrder.h"
#include "polarphp/pil/lang/PrettyStackTrace.h"
#include "polarphp/pil/lang/PILDebugScope.h"
#include "polarphp/pil/lang/PILFunction.h"
#include "polarphp/pil/lang/PILModule.h"
#include "polarphp/pil/lang/PILOpenedArchetypesTracker.h"
#include "polarphp/pil/lang/PILVTable.h"
#include "polarphp/pil/lang/PILVTableVisitor.h"
#include "polarphp/pil/lang/PILVisitor.h"
#include "polarphp/pil/lang/TypeLowering.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"

using namespace polar;

using lowering::AbstractionPattern;

// This flag is used only to check that sil-combine can properly
// remove any code after unreachable, thus bringing PIL into
// its canonical form which may get temporarily broken during
// intermediate transformations.
static llvm::cl::opt<bool> SkipUnreachableMustBeLastErrors(
   "verify-skip-unreachable-must-be-last",
   llvm::cl::init(false));

// This flag controls the default behaviour when hitting a verification
// failure (abort/exit).
static llvm::cl::opt<bool> AbortOnFailure(
   "verify-abort-on-failure",
   llvm::cl::init(true));

static llvm::cl::opt<bool> VerifyDIHoles(
   "verify-di-holes",
   llvm::cl::init(true));

static llvm::cl::opt<bool> SkipConvertEscapeToNoescapeAttributes(
   "verify-skip-convert-escape-to-noescape-attributes", llvm::cl::init(false));

// The verifier is basically all assertions, so don't compile it with NDEBUG to
// prevent release builds from triggering spurious unused variable warnings.

//===----------------------------------------------------------------------===//
//                                PILVerifier
//===----------------------------------------------------------------------===//

/// Returns true if A is an opened existential type or is equal to an
/// archetype from F's generic context.
static bool isArchetypeValidInFunction(ArchetypeType *A, const PILFunction *F) {
   auto root = dyn_cast<PrimaryArchetypeType>(A->getRoot());
   if (!root)
      return true;
   if (isa<OpenedArchetypeType>(A->getRoot()))
      return true;
   if (isa<OpaqueTypeArchetypeType>(A->getRoot()))
      return true;

   // Ok, we have a primary archetype, make sure it is in the nested generic
   // environment of our caller.
   if (auto *genericEnv = F->getGenericEnvironment())
      if (root->getGenericEnvironment() == genericEnv)
         return true;

   return false;
}

namespace {

/// Metaprogramming-friendly base class.
template <class Impl>
class PILVerifierBase : public PILInstructionVisitor<Impl> {
public:
   // visitCLASS calls visitPARENT and checkCLASS.
   // checkCLASS does nothing by default.
#define INST(CLASS, PARENT)                                     \
  void visit##CLASS(CLASS *I) {                                 \
    static_cast<Impl*>(this)->visit##PARENT(I);                 \
    static_cast<Impl*>(this)->check##CLASS(I);                  \
  }                                                             \
  void check##CLASS(CLASS *I) {}
#include "polarphp/pil/lang/PILNodesDef.h"

   void visitPILInstruction(PILInstruction *I) {
      static_cast<Impl*>(this)->checkPILInstruction(I);
   }
   void checkPILInstruction(PILInstruction *I) {}
};
} // end anonymous namespace

namespace {

/// Verify invariants on a key path component.
void verifyKeyPathComponent(PILModule &M,
                            ResilienceExpansion expansion,
                            llvm::function_ref<void(bool, StringRef)> require,
                            CanType &baseTy,
                            CanType leafTy,
                            const KeyPathPatternComponent &component,
                            ArrayRef<Operand> operands,
                            CanGenericSignature patternSig,
                            SubstitutionMap patternSubs,
                            bool forPropertyDescriptor,
                            bool hasIndices) {
   auto &C = M.getAstContext();
   auto typeExpansionContext =
      TypeExpansionContext::noOpaqueTypeArchetypesSubstitution(expansion);
   auto opaque = AbstractionPattern::getOpaque();
   auto loweredBaseTy =
      M.Types.getLoweredType(opaque, baseTy, typeExpansionContext);
   auto componentTy = component.getComponentType().subst(patternSubs)
      ->getCanonicalType();
   auto loweredComponentTy =
      M.Types.getLoweredType(opaque, componentTy, typeExpansionContext);

   auto checkIndexEqualsAndHash = [&]{
      if (!component.getSubscriptIndices().empty()) {
         // Equals should be
         // <Sig...> @convention(thin) (RawPointer, RawPointer) -> Bool
         {
            auto equals = component.getSubscriptIndexEquals();
            require(equals, "key path pattern with indexes must have equals "
                            "operator");

            auto substEqualsType = equals->getLoweredFunctionType()
               ->substGenericArgs(M, patternSubs, TypeExpansionContext::minimal());

            require(substEqualsType->getParameters().size() == 2,
                    "must have two arguments");
            for (unsigned i = 0; i < 2; ++i) {
               auto param = substEqualsType->getParameters()[i];
               require(param.getConvention()
                       == ParameterConvention::Direct_Unowned,
                       "indices pointer should be trivial");
               require(param.getInterfaceType()->getAnyNominal()
                       == C.getUnsafeRawPointerDecl(),
                       "indices pointer should be an UnsafeRawPointer");
            }

            require(substEqualsType->getResults().size() == 1,
                    "must have one result");

            require(substEqualsType->getResults()[0].getConvention()
                    == ResultConvention::Unowned,
                    "result should be unowned");
            require(substEqualsType->getResults()[0].getInterfaceType()
                       ->getAnyNominal()
                    == C.getBoolDecl(),
                    "result should be Bool");
         }
         {
            // Hash should be
            // <Sig...> @convention(thin) (RawPointer) -> Int
            auto hash = component.getSubscriptIndexHash();
            require(hash, "key path pattern with indexes must have hash "
                          "operator");

            auto substHashType = hash->getLoweredFunctionType()
               ->substGenericArgs(M, patternSubs, TypeExpansionContext::minimal());

            require(substHashType->getParameters().size() == 1,
                    "must have two arguments");
            auto param = substHashType->getParameters()[0];
            require(param.getConvention()
                    == ParameterConvention::Direct_Unowned,
                    "indices pointer should be trivial");
            require(param.getInterfaceType()->getAnyNominal()
                    == C.getUnsafeRawPointerDecl(),
                    "indices pointer should be an UnsafeRawPointer");

            require(substHashType->getResults().size() == 1,
                    "must have one result");

            require(substHashType->getResults()[0].getConvention()
                    == ResultConvention::Unowned,
                    "result should be unowned");
            require(substHashType->getResults()[0].getInterfaceType()
                       ->getAnyNominal()
                    == C.getIntDecl(),
                    "result should be Int");
         }
      } else {
         require(!component.getSubscriptIndexEquals()
                 && !component.getSubscriptIndexHash(),
                 "component without indexes must not have equals/hash");
      }
   };

   switch (auto kind = component.getKind()) {
      case KeyPathPatternComponent::Kind::StoredProperty: {
         auto property = component.getStoredPropertyDecl();
         if (expansion == ResilienceExpansion::Minimal) {
            require(property->getEffectiveAccess() >= AccessLevel::Public,
                    "Key path in serialized function cannot reference non-public "
                    "property");
         }

         auto fieldTy = baseTy->getTypeOfMember(M.getPolarphpModule(), property)
            ->getReferenceStorageReferent()
            ->getCanonicalType();
         require(fieldTy == componentTy,
                 "property decl should be a member of the base with the same type "
                 "as the component");
         require(property->hasStorage(), "property must be stored");
         require(!property->isResilient(M.getPolarphpModule(), expansion),
                 "cannot access storage of resilient property");
         auto propertyTy =
            loweredBaseTy.getFieldType(property, M, typeExpansionContext);
         require(propertyTy.getObjectType()
                 == loweredComponentTy.getObjectType(),
                 "component type should match the maximal abstraction of the "
                 "formal type");
         break;
      }

      case KeyPathPatternComponent::Kind::GettableProperty:
      case KeyPathPatternComponent::Kind::SettableProperty: {
         if (forPropertyDescriptor) {
            require(component.getSubscriptIndices().empty()
                    && !component.getSubscriptIndexEquals()
                    && !component.getSubscriptIndexHash(),
                    "property descriptor should not have index information");

            require(component.getExternalDecl() == nullptr
                    && component.getExternalSubstitutions().empty(),
                    "property descriptor should not refer to another external decl");
         } else {
            require(hasIndices == !component.getSubscriptIndices().empty(),
                    "component for subscript should have indices");
         }

         auto normalArgConvention = ParameterConvention::Indirect_In_Guaranteed;

         // Getter should be <Sig...> @convention(thin) (@in_guaranteed Base) -> @out Result
         {
            auto getter = component.getComputedPropertyGetter();
            if (expansion == ResilienceExpansion::Minimal) {
               require(getter->hasValidLinkageForFragileRef(),
                       "Key path in serialized function should not reference "
                       "less visible getters");
            }

            auto substGetterType = getter->getLoweredFunctionType()->substGenericArgs(
               M, patternSubs, TypeExpansionContext::minimal());
            require(substGetterType->getRepresentation() ==
                    PILFunctionTypeRepresentation::Thin,
                    "getter should be a thin function");

            require(substGetterType->getNumParameters() == 1 + hasIndices,
                    "getter should have one parameter");
            auto baseParam = substGetterType->getParameters()[0];
            require(baseParam.getConvention() == normalArgConvention,
                    "getter base parameter should have normal arg convention");
            require(baseParam.getArgumentType(M, substGetterType)
                    == loweredBaseTy.getAstType(),
                    "getter base parameter should match base of component");

            if (hasIndices) {
               auto indicesParam = substGetterType->getParameters()[1];
               require(indicesParam.getConvention()
                       == ParameterConvention::Direct_Unowned,
                       "indices pointer should be trivial");
               require(indicesParam.getArgumentType(M, substGetterType)->getAnyNominal()
                       == C.getUnsafeRawPointerDecl(),
                       "indices pointer should be an UnsafeRawPointer");
            }

            require(substGetterType->getNumResults() == 1,
                    "getter should have one result");
            auto result = substGetterType->getResults()[0];
            require(result.getConvention() == ResultConvention::Indirect,
                    "getter result should be @out");
            require(result.getReturnValueType(M, substGetterType)
                    == loweredComponentTy.getAstType(),
                    "getter result should match the maximal abstraction of the "
                    "formal component type");
         }

         if (kind == KeyPathPatternComponent::Kind::SettableProperty) {
            // Setter should be
            // <Sig...> @convention(thin) (@in_guaranteed Result, @in Base) -> ()

            auto setter = component.getComputedPropertySetter();
            if (expansion == ResilienceExpansion::Minimal) {
               require(setter->hasValidLinkageForFragileRef(),
                       "Key path in serialized function should not reference "
                       "less visible setters");
            }

            auto substSetterType = setter->getLoweredFunctionType()
               ->substGenericArgs(M, patternSubs, TypeExpansionContext::minimal());

            require(substSetterType->getRepresentation() ==
                    PILFunctionTypeRepresentation::Thin,
                    "setter should be a thin function");

            require(substSetterType->getNumParameters() == 2 + hasIndices,
                    "setter should have two parameters");

            auto newValueParam = substSetterType->getParameters()[0];
            // TODO: This should probably be unconditionally +1 when we
            // can represent that.
            require(newValueParam.getConvention() == normalArgConvention,
                    "setter value parameter should havee normal arg convention");

            auto baseParam = substSetterType->getParameters()[1];
            require(baseParam.getConvention() == normalArgConvention
                    || baseParam.getConvention() ==
                       ParameterConvention::Indirect_Inout,
                    "setter base parameter should be normal arg convention "
                    "or @inout");

            if (hasIndices) {
               auto indicesParam = substSetterType->getParameters()[2];
               require(indicesParam.getConvention()
                       == ParameterConvention::Direct_Unowned,
                       "indices pointer should be trivial");
               require(indicesParam.getArgumentType(M, substSetterType)->getAnyNominal()
                       == C.getUnsafeRawPointerDecl(),
                       "indices pointer should be an UnsafeRawPointer");
            }

            require(newValueParam.getArgumentType(M, substSetterType) ==
                    loweredComponentTy.getAstType(),
                    "setter value should match the maximal abstraction of the "
                    "formal component type");

            require(substSetterType->getNumResults() == 0,
                    "setter should have no results");
         }

         if (!forPropertyDescriptor) {
            for (auto &index : component.getSubscriptIndices()) {
               auto opIndex = index.Operand;
               auto contextType =
                  index.LoweredType.subst(M, patternSubs);
               require(contextType == operands[opIndex].get()->getType(),
                       "operand must match type required by pattern");
               PILType loweredType = index.LoweredType;
               require(
                  loweredType.isLoweringOf(typeExpansionContext, M, index.FormalType),
                  "pattern index formal type doesn't match lowered type");
            }

            checkIndexEqualsAndHash();
         }

         break;
      }
      case KeyPathPatternComponent::Kind::OptionalChain: {
         require(baseTy->getOptionalObjectType()->isEqual(componentTy),
                 "chaining component should unwrap optional");
         require((bool)leafTy->getOptionalObjectType(),
                 "key path with chaining component should have optional "
                 "result");
         break;
      }
      case KeyPathPatternComponent::Kind::OptionalForce: {
         require(baseTy->getOptionalObjectType()->isEqual(componentTy),
                 "forcing component should unwrap optional");
         break;
      }
      case KeyPathPatternComponent::Kind::OptionalWrap: {
         require(componentTy->getOptionalObjectType()->isEqual(baseTy),
                 "wrapping component should wrap optional");
         break;
      }
      case KeyPathPatternComponent::Kind::TupleElement: {
         require(loweredBaseTy.is<TupleType>(),
                 "invalid baseTy, should have been a TupleType");

         auto tupleTy = loweredBaseTy.castTo<TupleType>();
         auto eltIdx = component.getTupleIndex();

         require(eltIdx < tupleTy->getNumElements(),
                 "invalid element index, greater than # of tuple elements");

         auto eltTy = tupleTy.getElementType(eltIdx)
            .getReferenceStorageReferent();

         require(eltTy == componentTy,
                 "tuple element type should match the type of the component");

         break;
      }
   }

   baseTy = componentTy;
}

/// Check if according to the PIL language model this memory /must only/ be used
/// immutably. Today this is only applied to in_guaranteed arguments and
/// open_existential_addr. We should expand it as needed.
struct ImmutableAddressUseVerifier {
   SmallVector<Operand *, 32> worklist;

   bool isConsumingOrMutatingArgumentConvention(PILArgumentConvention conv) {
      switch (conv) {
         case PILArgumentConvention::Indirect_In_Guaranteed:
            return false;

         case PILArgumentConvention::Indirect_InoutAliasable:
            // DISCUSSION: We do not consider inout_aliasable to be "truly mutating"
            // since today it is just used as a way to mark a captured argument and
            // not that something truly has mutating semantics. The reason why this
            // is safe is that the typechecker guarantees that if our value was
            // immutable, then the use in the closure must be immutable as well.
            //
            // TODO: Remove this in favor of using Inout and In_Guaranteed.
            return false;

         case PILArgumentConvention::Indirect_Out:
         case PILArgumentConvention::Indirect_In:
         case PILArgumentConvention::Indirect_In_Constant:
         case PILArgumentConvention::Indirect_Inout:
            return true;

         case PILArgumentConvention::Direct_Unowned:
         case PILArgumentConvention::Direct_Guaranteed:
         case PILArgumentConvention::Direct_Owned:
         case PILArgumentConvention::Direct_Deallocating:
            assert(conv.isIndirectConvention() && "Expect an indirect convention");
            return true; // return something "conservative".
      }
      llvm_unreachable("covered switch isn't covered?!");
   }

   bool isConsumingOrMutatingApplyUse(Operand *use) {
      ApplySite apply(use->getUser());
      assert(apply && "Not an apply instruction kind");
      auto conv = apply.getArgumentConvention(*use);
      return isConsumingOrMutatingArgumentConvention(conv);
   }

   bool isConsumingOrMutatingYieldUse(Operand *use) {
      // For now, just say that it is non-consuming for now.
      auto *yield = cast<YieldInst>(use->getUser());
      auto conv = yield->getArgumentConventionForOperand(*use);
      return isConsumingOrMutatingArgumentConvention(conv);
   }

   // A "copy_addr %src [take] to *" is consuming on "%src".
   // A "copy_addr * to * %dst" is mutating on "%dst".
   bool isConsumingOrMutatingCopyAddrUse(Operand *use) {
      auto *copyAddr = cast<CopyAddrInst>(use->getUser());
      if (copyAddr->getDest() == use->get())
         return true;
      if (copyAddr->getSrc() == use->get() && copyAddr->isTakeOfSrc() == IsTake)
         return true;
      return false;
   }

   bool isCastToNonConsuming(UncheckedAddrCastInst *i) {
      // Check if any of our uses are consuming. If none of them are consuming, we
      // are good to go.
      return llvm::none_of(i->getUses(), [&](Operand *use) -> bool {
         auto *inst = use->getUser();
         switch (inst->getKind()) {
            default:
               return false;
            case PILInstructionKind::ApplyInst:
            case PILInstructionKind::TryApplyInst:
            case PILInstructionKind::PartialApplyInst:
            case PILInstructionKind::BeginApplyInst:
               return isConsumingOrMutatingApplyUse(use);
         }
      });
   }

   bool isMutatingOrConsuming(PILValue address) {
      llvm::copy(address->getUses(), std::back_inserter(worklist));
      while (!worklist.empty()) {
         auto *use = worklist.pop_back_val();
         auto *inst = use->getUser();

         if (inst->isTypeDependentOperand(*use))
            continue;

         // TODO: Can this switch be restructured so break -> error, continue ->
         // next iteration, return -> return the final result.
         switch (inst->getKind()) {
            case PILInstructionKind::BuiltinInst: {
               // If we are processing a polymorphic builtin that takes an address,
               // skip the builtin. This is because the builtin must be specialized to
               // a non-memory reading builtin that works on trivial object values
               // before the diagnostic passes end (or be DCEed) or we emit a
               // diagnostic.
               if (auto builtinKind = cast<BuiltinInst>(inst)->getBuiltinKind()) {
                  if (isPolymorphicBuiltin(*builtinKind)) {
                     break;
                  }
               }

               // Otherwise this is a builtin that we are not expecting to see, so bail
               // and assert.
               llvm::errs() << "Unhandled, unexpected builtin instruction: " << *inst;
               llvm_unreachable("invoking standard assertion failure");
               break;
            }
            case PILInstructionKind::MarkDependenceInst:
            case PILInstructionKind::LoadBorrowInst:
            case PILInstructionKind::DebugValueAddrInst:
            case PILInstructionKind::ExistentialMetatypeInst:
            case PILInstructionKind::ValueMetatypeInst:
            case PILInstructionKind::FixLifetimeInst:
            case PILInstructionKind::KeyPathInst:
            case PILInstructionKind::SwitchEnumAddrInst:
               break;
            case PILInstructionKind::AddressToPointerInst:
               // We assume that the user is attempting to do something unsafe since we
               // are converting to a raw pointer. So just ignore this use.
               //
               // TODO: Can we do better?
               break;
            case PILInstructionKind::BranchInst:
            case PILInstructionKind::CondBranchInst:
               // We do not analyze through branches and cond_br instructions and just
               // assume correctness. This is so that we can avoid having to analyze
               // through phi loops and since we want to remove address phis (meaning
               // that this eventually would never be able to happen). Once that
               // changes happens, we should remove this code and just error below.
               break;
            case PILInstructionKind::ApplyInst:
            case PILInstructionKind::TryApplyInst:
            case PILInstructionKind::PartialApplyInst:
            case PILInstructionKind::BeginApplyInst:
               if (isConsumingOrMutatingApplyUse(use))
                  return true;
               break;
            case PILInstructionKind::YieldInst:
               if (isConsumingOrMutatingYieldUse(use))
                  return true;
               break;
            case PILInstructionKind::CopyAddrInst:
               if (isConsumingOrMutatingCopyAddrUse(use))
                  return true;
               else
                  break;
            case PILInstructionKind::DestroyAddrInst:
               return true;
            case PILInstructionKind::UncheckedAddrCastInst: {
               if (isCastToNonConsuming(cast<UncheckedAddrCastInst>(inst))) {
                  break;
               }
               return true;
            }
            case PILInstructionKind::CheckedCastAddrBranchInst:
               switch (cast<CheckedCastAddrBranchInst>(inst)->getConsumptionKind()) {
                  case CastConsumptionKind::BorrowAlways:
                     llvm_unreachable("checked_cast_addr_br cannot have BorrowAlways");
                  case CastConsumptionKind::CopyOnSuccess:
                     break;
                  case CastConsumptionKind::TakeAlways:
                  case CastConsumptionKind::TakeOnSuccess:
                     return true;
               }
               break;
            case PILInstructionKind::LoadInst:
               // A 'non-taking' value load is harmless.
               if (cast<LoadInst>(inst)->getOwnershipQualifier() ==
                   LoadOwnershipQualifier::Take)
                  return true;
               break;
#define NEVER_OR_SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, ...)             \
  case PILInstructionKind::Load##Name##Inst:                                   \
    if (cast<Load##Name##Inst>(inst)->isTake())                                \
      return true;                                                             \
    break;
#include "polarphp/ast/ReferenceStorageDef.h"
            case PILInstructionKind::OpenExistentialAddrInst:
               // If we have a mutable use, return true. Otherwise fallthrough since we
               // want to look through immutable uses.
               if (cast<OpenExistentialAddrInst>(inst)->getAccessKind() !=
                   OpenedExistentialAccess::Immutable)
                  return true;
               LLVM_FALLTHROUGH;
            case PILInstructionKind::StructElementAddrInst:
            case PILInstructionKind::TupleElementAddrInst:
            case PILInstructionKind::IndexAddrInst:
            case PILInstructionKind::TailAddrInst:
            case PILInstructionKind::IndexRawPointerInst:
               // Add these to our worklist.
               for (auto result : inst->getResults()) {
                  llvm::copy(result->getUses(), std::back_inserter(worklist));
               }
               break;
            default:
               llvm::errs() << "Unhandled, unexpected instruction: " << *inst;
               llvm_unreachable("invoking standard assertion failure");
               break;
         }
      }
      return false;
   }
};

/// The PIL verifier walks over a PIL function / basic block / instruction,
/// checking and enforcing its invariants.
class PILVerifier : public PILVerifierBase<PILVerifier> {
   ModuleDecl *M;
   const PILFunction &F;
   PILFunctionConventions fnConv;
   lowering::TypeConverter &TC;
   PILOpenedArchetypesTracker OpenedArchetypes;
   SmallVector<StringRef, 16> DebugVars;
   const PILInstruction *CurInstruction = nullptr;
   const PILArgument *CurArgument = nullptr;
   std::unique_ptr<DominanceInfo> Dominance;

   // Used for dominance checking within a basic block.
   llvm::DenseMap<const PILInstruction *, unsigned> InstNumbers;

   DeadEndBlocks DEBlocks;
   bool SingleFunction = true;

   PILVerifier(const PILVerifier&) = delete;
   void operator=(const PILVerifier&) = delete;
public:
   bool isPILOwnershipEnabled() const {
      return F.getModule().getOptions().VerifyPILOwnership;
   }

   void _require(bool condition, const Twine &complaint,
                 const std::function<void()> &extraContext = nullptr) {
      if (condition) return;

      llvm::dbgs() << "PIL verification failed: " << complaint << "\n";

      if (extraContext) extraContext();

      if (CurInstruction) {
         llvm::dbgs() << "Verifying instruction:\n";
         CurInstruction->printInContext(llvm::dbgs());
      } else if (CurArgument) {
         llvm::dbgs() << "Verifying argument:\n";
         CurArgument->printInContext(llvm::dbgs());
      }
      llvm::dbgs() << "In function:\n";
      F.print(llvm::dbgs());

      // We abort by default because we want to always crash in
      // the debugger.
      if (AbortOnFailure)
         abort();
      else
         exit(1);
   }
#define require(condition, complaint) \
  _require(bool(condition), complaint ": " #condition)

   template <class T> typename CanTypeWrapperTraits<T>::type
   _requireObjectType(PILType type, const Twine &valueDescription,
                      const char *typeName) {
      _require(type.isObject(), valueDescription + " must be an object");
      auto result = type.getAs<T>();
      _require(bool(result), valueDescription + " must have type " + typeName);
      return result;
   }
   template <class T> typename CanTypeWrapperTraits<T>::type
   _requireObjectType(PILValue value, const Twine &valueDescription,
                      const char *typeName) {
      return _requireObjectType<T>(value->getType(), valueDescription, typeName);
   }
#define requireObjectType(type, value, valueDescription) \
  _requireObjectType<type>(value, valueDescription, #type)

   template <class T> typename CanTypeWrapperTraits<T>::type
   _requireAddressType(PILType type, const Twine &valueDescription,
                       const char *typeName) {
      _require(type.isAddress(), valueDescription + " must be an address");
      auto result = type.getAs<T>();
      _require(bool(result), valueDescription + " must have type " + typeName);
      return result;
   }
   template <class T> typename CanTypeWrapperTraits<T>::type
   _requireAddressType(PILValue value, const Twine &valueDescription,
                       const char *typeName) {
      return _requireAddressType<T>(value->getType(), valueDescription, typeName);
   }
#define requireAddressType(type, value, valueDescription) \
  _requireAddressType<type>(value, valueDescription, #type)

   template <class T>
   typename CanTypeWrapperTraits<T>::type
   _forbidObjectType(PILType type, const Twine &valueDescription,
                     const char *typeName) {
      _require(type.isObject(), valueDescription + " must be an object");
      auto result = type.getAs<T>();
      _require(!bool(result),
               valueDescription + " must not have type " + typeName);
      return result;
   }
   template <class T>
   typename CanTypeWrapperTraits<T>::type
   _forbidObjectType(PILValue value, const Twine &valueDescription,
                     const char *typeName) {
      return _forbidObjectType<T>(value->getType(), valueDescription, typeName);
   }
#define forbidObjectType(type, value, valueDescription)                        \
  _forbidObjectType<type>(value, valueDescription, #type)

   // Require that the operand is a non-optional, non-unowned reference-counted
   // type.
   void requireReferenceValue(PILValue value, const Twine &valueDescription) {
      require(value->getType().isObject(), valueDescription +" must be an object");
      require(value->getType().isReferenceCounted(F.getModule()),
              valueDescription + " must have reference semantics");
      forbidObjectType(UnownedStorageType, value, valueDescription);
   }

   // Require that the operand is a reference-counted type, or an Optional
   // thereof.
   void requireReferenceOrOptionalReferenceValue(PILValue value,
                                                 const Twine &valueDescription) {
      require(value->getType().isObject(), valueDescription +" must be an object");

      auto objectTy = value->getType().unwrapOptionalType();

      require(objectTy.isReferenceCounted(F.getModule()),
              valueDescription + " must have reference semantics");
   }

   // Require that the operand is a type that supports reference storage
   // modifiers.
   void requireReferenceStorageCapableValue(PILValue value,
                                            const Twine &valueDescription) {
      requireReferenceOrOptionalReferenceValue(value, valueDescription);
      require(!value->getType().is<PILFunctionType>(),
              valueDescription + " cannot apply to a function type");
   }

   /// Assert that two types are equal.
   void requireSameType(PILType type1, PILType type2, const Twine &complaint) {
      _require(type1 == type2, complaint, [&] {
         llvm::dbgs() << "  " << type1 << "\n  " << type2 << '\n';
      });
   }

   /// Require two function types to be ABI-compatible.
   void requireABICompatibleFunctionTypes(CanPILFunctionType type1,
                                          CanPILFunctionType type2,
                                          const Twine &what,
                                          PILFunction &inFunction) {
      auto complain = [=](const char *msg) -> std::function<void()> {
         return [=]{
            llvm::dbgs() << "  " << msg << '\n'
                         << "  " << type1 << "\n  " << type2 << '\n';
         };
      };
      auto complainBy = [=](std::function<void()> msg) -> std::function<void()> {
         return [=]{
            msg();
            llvm::dbgs() << '\n';
            llvm::dbgs() << "  " << type1 << "\n  " << type2 << '\n';
         };
      };

      // If we didn't have a failure, return.
      auto Result = type1->isABICompatibleWith(type2, inFunction);
      if (Result.isCompatible())
         return;

      if (!Result.hasPayload()) {
         _require(false, what, complain(Result.getMessage().data()));
      } else {
         _require(false, what, complainBy([=] {
            llvm::dbgs() << " " << Result.getMessage().data()
                         << ".\nParameter: " << Result.getPayload();
         }));
      }
   }

   void requireSameFunctionComponents(CanPILFunctionType type1,
                                      CanPILFunctionType type2,
                                      const Twine &what) {
      require(type1->getNumResults() == type2->getNumResults(),
              "results of " + what + " do not match in count");
      for (auto i : indices(type1->getResults())) {
         require(type1->getResults()[i] == type2->getResults()[i],
                 "result " + Twine(i) + " of " + what + " do not match");
      }
      require(type1->getParameters().size() ==
              type2->getParameters().size(),
              "inputs of " + what + " do not match in count");
      for (auto i : indices(type1->getParameters())) {
         require(type1->getParameters()[i] ==
                 type2->getParameters()[i],
                 "input " + Twine(i) + " of " + what + " do not match");
      }
   }

   static unsigned numInstsInFunction(const PILFunction &F) {
      unsigned numInsts = 0;
      for (auto &BB : F) {
         numInsts += std::distance(BB.begin(), BB.end());
      }
      return numInsts;
   }

   PILVerifier(const PILFunction &F, bool SingleFunction = true)
      : M(F.getModule().getPolarphpModule()), F(F),
        fnConv(F.getLoweredFunctionType(), F.getModule()),
        TC(F.getModule().Types), OpenedArchetypes(&F), Dominance(nullptr),
        InstNumbers(numInstsInFunction(F)),
        DEBlocks(&F), SingleFunction(SingleFunction) {
      if (F.isExternalDeclaration())
         return;

      // Check to make sure that all blocks are well formed.  If not, the
      // PILVerifier object will explode trying to compute dominance info.
      unsigned InstIdx = 0;
      for (auto &BB : F) {
         require(!BB.empty(), "Basic blocks cannot be empty");
         require(isa<TermInst>(BB.back()),
                 "Basic blocks must end with a terminator instruction");
         for (auto &I : BB)
            InstNumbers[&I] = InstIdx++;
      }

      Dominance.reset(new DominanceInfo(const_cast<PILFunction *>(&F)));

      auto *DebugScope = F.getDebugScope();
      require(DebugScope, "All PIL functions must have a debug scope");
      require(DebugScope->Parent.get<PILFunction *>() == &F,
              "Scope of PIL function points to different function");
   }

   // Checks dominance between two instructions.
   // This does not use DominanceInfo.properlyDominates, because for large basic
   // blocks it would result in quadratic behavior.
   bool properlyDominates(PILInstruction *a, PILInstruction *b) {
      auto aBlock = a->getParent(), bBlock = b->getParent();

      // If the blocks are different, it's as easy as whether A's block
      // dominates B's block.
      if (aBlock != bBlock)
         return Dominance->properlyDominates(aBlock, bBlock);

      return InstNumbers[a] < InstNumbers[b];
   }

   // FIXME: For sanity, address-type block args should be prohibited at all PIL
   // stages. However, the optimizer currently breaks the invariant in three
   // places:
   // 1. Normal Simplify CFG during conditional branch simplification
   //    (sneaky jump threading).
   // 2. Simplify CFG via Jump Threading.
   // 3. Loop Rotation.
   //
   //
   bool prohibitAddressBlockArgs() {
      // If this function was deserialized from canonical PIL, this invariant may
      // already have been violated regardless of this module's PIL stage or
      // exclusivity enforcement level. Presumably, access markers were already
      // removed prior to serialization.
      if (F.wasDeserializedCanonical())
         return false;

      PILModule &M = F.getModule();
      return M.getStage() == PILStage::Raw;
   }

   void visitPILPhiArgument(PILPhiArgument *arg) {
      // Verify that the `isPhiArgument` property is sound:
      // - Phi arguments come from branches.
      // - Non-phi arguments have a single predecessor.
      if (arg->isPhiArgument()) {
         for (PILBasicBlock *predBB : arg->getParent()->getPredecessorBlocks()) {
            auto *TI = predBB->getTerminator();
            // FIXME: when critical edges are removed, only allow BranchInst.
            require(isa <BranchInst>(TI) || isa<CondBranchInst>(TI),
                    "All phi argument inputs must be from branches.");
         }
      } else {
      }
      if (arg->isPhiArgument() && prohibitAddressBlockArgs()) {
         // As a property of well-formed PIL, we disallow address-type block
         // arguments. Supporting them would prevent reliably reasoning about the
         // underlying storage of memory access. This reasoning is important for
         // diagnosing violations of memory access rules and supporting future
         // optimizations such as bitfield packing. Address-type block arguments
         // also create unnecessary complexity for PIL optimization passes that
         // need to reason about memory aliasing.
         require(!arg->getType().isAddress(),
                 "Block arguments cannot be addresses");
      }
   }

   void visitPILArgument(PILArgument *arg) {
      CurArgument = arg;
      checkLegalType(arg->getFunction(), arg, nullptr);
      checkValueBaseOwnership(arg);
      if (auto *phiArg = dyn_cast<PILPhiArgument>(arg)) {
         if (phiArg->isPhiArgument())
            visitPILPhiArgument(phiArg);
         else {
            // A non-phi BlockArgument must have a single predecessor unless it is
            // unreachable.
            require(arg->getParent()->pred_empty()
                    || arg->getParent()->getSinglePredecessorBlock(),
                    "Non-branch terminator must have a unique successor.");
         }
         return;
      }

      // If we are not in lowered PIL and have an in_guaranteed function argument,
      // verify that we do not mutate or consume it.
      auto *fArg = cast<PILFunctionArgument>(arg);
      if (fArg->getModule().getStage() == PILStage::Lowered ||
          !fArg->getType().isAddress() ||
          !fArg->hasConvention(PILArgumentConvention::Indirect_In_Guaranteed))
         return;

      require(!ImmutableAddressUseVerifier().isMutatingOrConsuming(fArg),
              "Found mutating or consuming use of an in_guaranteed parameter?!");
   }

   void visitPILInstruction(PILInstruction *I) {
      CurInstruction = I;
      OpenedArchetypes.registerOpenedArchetypes(I);
      checkPILInstruction(I);

      // Check the PILLLocation attached to the instruction.
      checkInstructionsPILLocation(I);

      // Check ownership.
      PILFunction *F = I->getFunction();
      assert(F && "Expected value base with parent function");

      for (auto result : I->getResults()) {
         checkLegalType(F, result, I);
         checkValueBaseOwnership(result);
      }
   }

   void checkValueBaseOwnership(ValueBase *V) {
      // If ownership is not enabled, bail.
      if (!isPILOwnershipEnabled())
         return;

      PILFunction *F = V->getFunction();
      assert(F && "Expected value base with parent function");
      // If we do not have qualified ownership, then do not verify value base
      // ownership.
      if (!F->hasOwnership())
         return;
      PILValue(V).verifyOwnership(&DEBlocks);
   }

   void checkPILInstruction(PILInstruction *I) {
      const PILBasicBlock *BB = I->getParent();
      require(BB, "Instruction with null parent");

      // Check that non-terminators look ok.
      if (!isa<TermInst>(I)) {
         require(!BB->empty(), "Can't be in a parent block if it is empty");
         if (!I->isStaticInitializerInst()) {
            require(&*BB->rbegin() != I,
                    "Non-terminators cannot be the last in a block");
         }
      } else {
         // Skip the check for UnreachableInst, if explicitly asked to do so.
         if (!isa<UnreachableInst>(I) || !SkipUnreachableMustBeLastErrors)
            require(&*BB->rbegin() == I,
                    "Terminator must be the last in block");
      }

      // Verify that all of our uses are in this function.
      for (auto result : I->getResults()) {
         for (Operand *use : result->getUses()) {
            auto user = use->getUser();
            require(user, "instruction user is null?");
            require(isa<PILInstruction>(user),
                    "instruction used by non-instruction");
            auto userI = cast<PILInstruction>(user);
            require(userI->getParent(),
                    "instruction used by unparented instruction");
            if (I->isStaticInitializerInst()) {
               require(userI->getParent() == BB,
                       "instruction used by instruction not in same static initializer");
            } else {
               require(userI->getFunction() == &F,
                       "instruction used by instruction in different function");
            }

            auto operands = userI->getAllOperands();
            require(operands.begin() <= use && use <= operands.end(),
                    "use doesn't actually belong to instruction it claims to");
         }
      }

      // Verify some basis structural stuff about an instruction's operands.
      for (auto &operand : I->getAllOperands()) {
         require(operand.get(), "instruction has null operand");

         if (auto *valueI = operand.get()->getDefiningInstruction()) {
            require(valueI->getParent(),
                    "instruction uses value of unparented instruction");
            if (I->isStaticInitializerInst()) {
               require(valueI->getParent() == BB,
                       "instruction uses value which is not in same static initializer");
            } else {
               require(valueI->getFunction() == &F,
                       "instruction uses value of instruction from another function");
               require(properlyDominates(valueI, I),
                       "instruction isn't dominated by its operand");
            }
         }

         if (auto *valueBBA = dyn_cast<PILArgument>(operand.get())) {
            require(!I->isStaticInitializerInst(),
                    "static initializer inst cannot refer to PILArgument");
            require(valueBBA->getParent(),
                    "instruction uses value of unparented instruction");
            require(valueBBA->getFunction() == &F,
                    "bb argument value from another function");
            require(Dominance->dominates(valueBBA->getParent(), I->getParent()),
                    "instruction isn't dominated by its bb argument operand");
         }

         require(operand.getUser() == I,
                 "instruction's operand's owner isn't the instruction");
         require(isInValueUses(&operand), "operand value isn't used by operand");

         if (I->isTypeDependentOperand(operand)) {
            require(isa<PILInstruction>(I),
                    "opened archetype operand should refer to a PILInstruction");
         }

         // Make sure that if operand is generic that its primary archetypes match
         // the function context.
         checkLegalType(I->getFunction(), operand.get(), I);
      }

      // TODO: There should be a use of an opened archetype inside the instruction for
      // each opened archetype operand of the instruction.
   }

   void checkInstructionsPILLocation(PILInstruction *I) {
      // Check the debug scope.
      auto *DS = I->getDebugScope();
      if (DS && !maybeScopeless(*I))
         require(DS, "instruction has a location, but no scope");

      require(!DS || DS->getParentFunction() == I->getFunction(),
              "debug scope of instruction belongs to a different function");

      // Check the location kind.
      PILLocation L = I->getLoc();
      PILLocation::LocationKind LocKind = L.getKind();
      PILInstructionKind InstKind = I->getKind();

      // Check that there is at most one debug variable defined
      // for each argument slot. This catches PIL transformations
      // that accidentally remove inline information (stored in the PILDebugScope)
      // from debug-variable-carrying instructions.
      if (!DS->InlinedCallSite) {
         Optional<PILDebugVariable> VarInfo;
         if (auto *DI = dyn_cast<AllocStackInst>(I))
            VarInfo = DI->getVarInfo();
         else if (auto *DI = dyn_cast<AllocBoxInst>(I))
            VarInfo = DI->getVarInfo();
         else if (auto *DI = dyn_cast<DebugValueInst>(I))
            VarInfo = DI->getVarInfo();
         else if (auto *DI = dyn_cast<DebugValueAddrInst>(I))
            VarInfo = DI->getVarInfo();

         if (VarInfo)
            if (unsigned ArgNo = VarInfo->ArgNo) {
               // It is a function argument.
               if (ArgNo < DebugVars.size() && !DebugVars[ArgNo].empty()) {
                  require(
                     DebugVars[ArgNo] == VarInfo->Name,
                     "Scope contains conflicting debug variables for one function "
                     "argument");
               } else {
                  // Reserve enough space.
                  while (DebugVars.size() <= ArgNo) {
                     DebugVars.push_back(StringRef());
                  }
               }
               DebugVars[ArgNo] = VarInfo->Name;
            }
      }

      // Regular locations are allowed on all instructions.
      if (LocKind == PILLocation::RegularKind)
         return;

      if (LocKind == PILLocation::ReturnKind ||
          LocKind == PILLocation::ImplicitReturnKind)
         require(InstKind == PILInstructionKind::BranchInst ||
                 InstKind == PILInstructionKind::ReturnInst ||
                 InstKind == PILInstructionKind::UnreachableInst,
                 "return locations are only allowed on branch and return instructions");

      if (LocKind == PILLocation::ArtificialUnreachableKind)
         require(InstKind == PILInstructionKind::UnreachableInst,
                 "artificial locations are only allowed on Unreachable instructions");
   }

   /// Check that the types of this value producer are all legal in the function
   /// context in which it exists.
   void checkLegalType(PILFunction *F, ValueBase *value, PILInstruction *I) {
      PILType type = value->getType();
      if (type.is<PILTokenType>()) {
         require(isLegalPILTokenProducer(value),
                 "PIL tokens can only be produced as the results of specific "
                 "instructions");
         return;
      }

      checkLegalType(F, type, I);
   }

   static bool isLegalPILTokenProducer(PILValue value) {
      if (auto beginApply = dyn_cast<BeginApplyResult>(value))
         return beginApply->isTokenResult();

      // Add more token cases here as they arise.

      return false;
   }

   /// Check that the given type is a legal PIL value type.
   void checkLegalType(PILFunction *F, PILType type, PILInstruction *I) {
      checkLegalPILType(F, type.getAstType(), I);
   }

   /// Check that the given type is a legal PIL value type.
   void checkLegalPILType(PILFunction *F, CanType rvalueType, PILInstruction *I) {
      // These types should have been removed by lowering.
      require(!isa<LValueType>(rvalueType),
              "l-value types are not legal in PIL");
      require(!isa<AnyFunctionType>(rvalueType),
              "AST function types are not legal in PIL");

      // Tuples should have had their element lowered.
      if (auto tuple = dyn_cast<TupleType>(rvalueType)) {
         for (auto eltTy : tuple.getElementTypes()) {
            checkLegalPILType(F, eltTy, I);
         }
         return;
      }

      // Optionals should have had their objects lowered.
      if (auto objectType = rvalueType.getOptionalObjectType()) {
         return checkLegalPILType(F, objectType, I);
      }

      // Metatypes should have explicit representations.
      if (auto metatype = dyn_cast<AnyMetatypeType>(rvalueType)) {
         require(metatype->hasRepresentation(),
                 "metatypes in PIL must have a representation");;
         // fallthrough for archetype check
      }

      rvalueType.visit([&](CanType t) {
         auto A = dyn_cast<ArchetypeType>(t);
         if (!A)
            return;
         require(isArchetypeValidInFunction(A, F),
                 "Operand is of an ArchetypeType that does not exist in the "
                 "Caller's generic param list.");
         if (auto OpenedA = getOpenedArchetypeOf(A)) {
            auto Def = OpenedArchetypes.getOpenedArchetypeDef(OpenedA);
            require (Def, "Opened archetype should be registered in PILFunction");
            require(I == nullptr || Def == I ||
                    properlyDominates(cast<PILInstruction>(Def), I),
                    "Use of an opened archetype should be dominated by a "
                    "definition of this opened archetype");
         }
      });
   }

   /// Check that this operand appears in the use-chain of the value it uses.
   static bool isInValueUses(const Operand *operand) {
      for (auto use : operand->get()->getUses())
         if (use == operand)
            return true;
      return false;
   }

   /// \return True if all of the users of the AllocStack instruction \p ASI are
   /// inside the same basic block.
   static bool isSingleBlockUsage(AllocStackInst *ASI, DominanceInfo *Dominance){
      PILBasicBlock *BB = ASI->getParent();
      for (auto UI = ASI->use_begin(), E = ASI->use_end(); UI != E; ++UI)
         if (UI->getUser()->getParent() != BB &&
             Dominance->isReachableFromEntry(UI->getUser()->getParent()))
            return false;

      return true;
   }

   void checkAllocStackInst(AllocStackInst *AI) {
      require(AI->getType().isAddress(),
              "result of alloc_stack must be an address type");

      verifyOpenedArchetype(AI, AI->getElementType().getAstType());

      // There used to be a check if all uses of ASI are inside the alloc-dealloc
      // range. But apparently it can be the case that ASI has uses after the
      // dealloc_stack. This can come up if the source contains a
      // withUnsafePointer where the pointer escapes.
      // It's illegal code but the compiler should not crash on it.
   }

   void checkAllocRefBase(AllocRefInstBase *ARI) {
      requireReferenceValue(ARI, "Result of alloc_ref");
      verifyOpenedArchetype(ARI, ARI->getType().getAstType());
      auto Types = ARI->getTailAllocatedTypes();
      auto Counts = ARI->getTailAllocatedCounts();
      unsigned NumTypes = Types.size();
      require(NumTypes == Counts.size(), "Mismatching types and counts");
      require(NumTypes == 0 || !ARI->isObjC(),
              "Can't tail allocate with ObjC class");
      for (unsigned Idx = 0; Idx < NumTypes; ++Idx) {
         verifyOpenedArchetype(ARI, Types[Idx].getAstType());
         require(Counts[Idx].get()->getType().is<BuiltinIntegerType>(),
                 "count needs integer type");
      }
   }

   void checkAllocRefInst(AllocRefInst *AI) {
      require(AI->isObjC() || AI->getType().getClassOrBoundGenericClass(),
              "alloc_ref must allocate class");
      checkAllocRefBase(AI);
   }

   void checkAllocRefDynamicInst(AllocRefDynamicInst *ARDI) {
      PILValue Metadata = ARDI->getMetatypeOperand();
      require(Metadata->getType().is<AnyMetatypeType>(),
              "operand of alloc_ref_dynamic must be of metatype type");
      auto metaTy = Metadata->getType().castTo<AnyMetatypeType>();
      require(metaTy->hasRepresentation(),
              "operand of alloc_ref_dynamic must have a metatype representation");
      if (ARDI->isObjC()) {
         require(metaTy->getRepresentation() == MetatypeRepresentation::ObjC,
                 "alloc_ref_dynamic @objc requires operand of ObjC metatype");
      } else {
         require(metaTy->getRepresentation() == MetatypeRepresentation::Thick,
                 "alloc_ref_dynamic requires operand of thick metatype");
      }
      checkAllocRefBase(ARDI);
   }

   /// Check the substitutions passed to an apply or partial_apply.
   CanPILFunctionType checkApplySubstitutions(SubstitutionMap subs,
                                              PILType calleeTy) {
      auto fnTy = requireObjectType(PILFunctionType, calleeTy, "callee operand");

      // If there are substitutions, verify them and apply them to the callee.
      if (!subs.hasAnySubstitutableParams()) {
         require(!fnTy->isPolymorphic(),
                 "callee of apply without substitutions must not be polymorphic");
         return fnTy;
      }
      require(fnTy->isPolymorphic(),
              "callee of apply with substitutions must be polymorphic");

      // Each archetype occurring in the substitutions list should belong to the
      // current function.
      for (auto replacementType : subs.getReplacementTypes()) {
         replacementType->getCanonicalType().visit([&](CanType t) {
            auto A = dyn_cast<ArchetypeType>(t);
            if (!A)
               return;
            require(isArchetypeValidInFunction(A, &F),
                    "Replacement type of a substitution contains an ArchetypeType "
                    "that does not exist in the Caller's generic param list.");
         });
      }

      // Apply the substitutions.
      return fnTy->substGenericArgs(F.getModule(), subs, F.getTypeExpansionContext());
   }

   /// Check that for each opened archetype or dynamic self type in substitutions
   /// or the calle type, there is a type dependent operand.
   void checkApplyTypeDependentArguments(ApplySite AS) {
      PILInstruction *AI = AS.getInstruction();

      llvm::DenseSet<ArchetypeType *> FoundOpenedArchetypes;
      unsigned hasDynamicSelf = 0;

      // Function to collect opened archetypes in FoundOpenedArchetypes and set
      // hasDynamicSelf.
      auto HandleType = [&](CanType Ty) {
         if (Ty->isOpenedExistential()) {
            auto A = cast<ArchetypeType>(Ty);
            require(isArchetypeValidInFunction(A, AI->getFunction()),
                    "Archetype to be substituted must be valid in function.");
            // Collect all opened archetypes used in the substitutions list.
            FoundOpenedArchetypes.insert(A);
            // Also check that they are properly tracked inside the current
            // function.
            auto Def = OpenedArchetypes.getOpenedArchetypeDef(A);
            require(Def, "Opened archetype should be registered in PILFunction");
            require(Def == AI ||
                    properlyDominates(cast<PILInstruction>(Def), AI),
                    "Use of an opened archetype should be dominated by a "
                    "definition of this opened archetype");
         }
         if (Ty->hasDynamicSelfType()) {
            hasDynamicSelf = 1;
         }
      };

      // Search for opened archetypes and dynamic self.
      for (auto Replacement : AS.getSubstitutionMap().getReplacementTypes()) {
         Replacement->getCanonicalType().visit(HandleType);
      }
      AS.getSubstCalleeType().visit(HandleType);

      require(FoundOpenedArchetypes.size() + hasDynamicSelf ==
              AI->getTypeDependentOperands().size(),
              "Number of opened archetypes and dynamic self in the substitutions "
              "list should match the number of type dependent operands");

      for (auto &Op : AI->getTypeDependentOperands()) {
         auto V = Op.get();
         if (isa<PILArgument>(V)) {
            require(hasDynamicSelf,
                    "dynamic self operand without dynamic self type");
            require(AI->getFunction()->hasSelfMetadataParam(),
                    "self metadata operand in function without self metadata param");
            require((ValueBase *)V == AI->getFunction()->getSelfMetadataArgument(),
                    "wrong self metadata operand");
         } else {
            require(isa<SingleValueInstruction>(V),
                    "opened archetype operand should refer to a PIL instruction");
            auto Archetype = getOpenedArchetypeOf(cast<SingleValueInstruction>(V));
            require(Archetype,
                    "opened archetype operand should define an opened archetype");
            require(FoundOpenedArchetypes.count(Archetype),
                    "opened archetype operand does not correspond to any opened "
                    "archetype from the substitutions list");
         }
      }
   }

   void checkFullApplySite(FullApplySite site) {
      checkApplyTypeDependentArguments(site);

      // Then make sure that we have a type that can be substituted for the
      // callee.
      auto substTy = checkApplySubstitutions(site.getSubstitutionMap(),
                                             site.getCallee()->getType());
      require(site.getOrigCalleeType()->getRepresentation() ==
              site.getSubstCalleeType()->getRepresentation(),
              "calling convention difference between types");

      require(!site.getSubstCalleeType()->isPolymorphic(),
              "substituted callee type should not be generic");

      requireSameType(PILType::getPrimitiveObjectType(substTy),
                      PILType::getPrimitiveObjectType(site.getSubstCalleeType()),
                      "substituted callee type does not match substitutions");

      // Check that the arguments and result match.
      PILFunctionConventions substConv(substTy, F.getModule());
      //require(site.getArguments().size() == substTy->getNumPILArguments(),
      require(site.getNumArguments() == substConv.getNumPILArguments(),
              "apply doesn't have right number of arguments for function");
      for (size_t i = 0, size = site.getNumArguments(); i < size; ++i) {
         requireSameType(site.getArguments()[i]->getType(),
                         substConv.getPILArgumentType(i),
                         "operand of 'apply' doesn't match function input type");
      }
   }

   void checkApplyInst(ApplyInst *AI) {
      checkFullApplySite(AI);

      PILFunctionConventions calleeConv(AI->getSubstCalleeType(), F.getModule());
      require(AI->getType() == calleeConv.getPILResultType(),
              "type of apply instruction doesn't match function result type");
      if (AI->isNonThrowing()) {
         require(calleeConv.funcTy->hasErrorResult(),
                 "nothrow flag used for callee without error result");
      } else {
         require(!calleeConv.funcTy->hasErrorResult(),
                 "apply instruction cannot call function with error result");
      }

      require(!calleeConv.funcTy->isCoroutine(),
              "cannot call coroutine with normal apply");

      // Check that if the apply is of a noreturn callee, make sure that an
      // unreachable is the next instruction.
      if (AI->getModule().getStage() == PILStage::Raw ||
          !AI->isCalleeNoReturn())
         return;
      require(isa<UnreachableInst>(std::next(PILBasicBlock::iterator(AI))),
              "No return apply without an unreachable as a next instruction.");
   }

   void checkTryApplyInst(TryApplyInst *AI) {
      checkFullApplySite(AI);

      PILFunctionConventions calleeConv(AI->getSubstCalleeType(), F.getModule());

      require(!calleeConv.funcTy->isCoroutine(),
              "cannot call coroutine with normal apply");

      auto normalBB = AI->getNormalBB();
      require(normalBB->args_size() == 1,
              "normal destination of try_apply must take one argument");
      requireSameType((*normalBB->args_begin())->getType(),
                      calleeConv.getPILResultType(),
                      "normal destination of try_apply must take argument "
                      "of normal result type");

      auto errorBB = AI->getErrorBB();
      require(calleeConv.funcTy->hasErrorResult(),
              "try_apply must call function with error result");
      require(errorBB->args_size() == 1,
              "error destination of try_apply must take one argument");
      requireSameType((*errorBB->args_begin())->getType(),
                      calleeConv.getPILErrorType(),
                      "error destination of try_apply must take argument "
                      "of error result type");
   }

   void checkBeginApplyInst(BeginApplyInst *AI) {
      checkFullApplySite(AI);

      PILFunctionConventions calleeConv(AI->getSubstCalleeType(), F.getModule());
      auto yieldResults = AI->getYieldedValues();
      auto yields = calleeConv.getYields();
      require(yields.size() == yieldResults.size(),
              "length mismatch in callee yields vs. begin_apply results");
      for (auto i : indices(yields)) {
         require(yieldResults[i]->getType() == calleeConv.getPILType(yields[i]),
                 "callee yield type does not match begin_apply result type");
      }

      if (AI->isNonThrowing()) {
         require(calleeConv.funcTy->hasErrorResult(),
                 "nothrow flag used for callee without error result");
      } else {
         require(!calleeConv.funcTy->hasErrorResult(),
                 "begin_apply instruction cannot call function with error result");
      }

      require(calleeConv.funcTy->getCoroutineKind() == PILCoroutineKind::YieldOnce,
              "must call yield_once coroutine with begin_apply");
   }

   void checkAbortApplyInst(AbortApplyInst *AI) {
      require(isa<BeginApplyResult>(AI->getOperand()) &&
              cast<BeginApplyResult>(AI->getOperand())->isTokenResult(),
              "operand of abort_apply must be a begin_apply");
   }

   void checkEndApplyInst(EndApplyInst *AI) {
      require(isa<BeginApplyResult>(AI->getOperand()) &&
              cast<BeginApplyResult>(AI->getOperand())->isTokenResult(),
              "operand of end_apply must be a begin_apply");
   }

   void verifyLLVMIntrinsic(BuiltinInst *BI, llvm::Intrinsic::ID ID) {
      // Certain llvm intrinsic require constant values as their operands.
      // Consequently, these must not be phi nodes (aka. basic block arguments).
      switch (ID) {
         default:
            break;
         case llvm::Intrinsic::ctlz: // llvm.ctlz
         case llvm::Intrinsic::cttz: // llvm.cttz
            break;
         case llvm::Intrinsic::memcpy:
         case llvm::Intrinsic::memmove:
         case llvm::Intrinsic::memset:
            require(!isa<PILArgument>(BI->getArguments()[3]),
                    "isvolatile argument of memory intrinsics must be an integer "
                    "literal");
            break;
         case llvm::Intrinsic::lifetime_start:
         case llvm::Intrinsic::lifetime_end:
         case llvm::Intrinsic::invariant_start:
            require(!isa<PILArgument>(BI->getArguments()[0]),
                    "size argument of memory use markers must be an integer literal");
            break;
         case llvm::Intrinsic::invariant_end:
            require(!isa<PILArgument>(BI->getArguments()[1]),
                    "llvm.invariant.end parameter #2 must be an integer literal");
            break;
      }
   }

   void checkPartialApplyInst(PartialApplyInst *PAI) {
      auto resultInfo = requireObjectType(PILFunctionType, PAI,
                                          "result of partial_apply");
      verifyPILFunctionType(resultInfo);
      require(resultInfo->getExtInfo().hasContext(),
              "result of closure cannot have a thin function type");

      checkApplyTypeDependentArguments(PAI);

      auto substTy = checkApplySubstitutions(PAI->getSubstitutionMap(),
                                             PAI->getCallee()->getType());

      require(!PAI->getSubstCalleeType()->isPolymorphic(),
              "substituted callee type should not be generic");

      requireSameType(PILType::getPrimitiveObjectType(substTy),
                      PILType::getPrimitiveObjectType(PAI->getSubstCalleeType()),
                      "substituted callee type does not match substitutions");

      // The arguments must match the suffix of the original function's input
      // types.
      require(PAI->getArguments().size() +
              resultInfo->getParameters().size()
              == substTy->getParameters().size(),
              "result of partial_apply should take as many inputs as were not "
              "applied by the instruction");

      PILFunctionConventions substConv(substTy, F.getModule());
      unsigned appliedArgStartIdx =
         substConv.getNumPILArguments() - PAI->getNumArguments();
      for (unsigned i = 0, size = PAI->getArguments().size(); i < size; ++i) {
         require(PAI->getArguments()[i]->getType()
                 == substConv.getPILArgumentType(appliedArgStartIdx + i),
                 "applied argument types do not match suffix of function type's "
                 "inputs");
      }

      // The arguments to the result function type must match the prefix of the
      // original function's input types.
      for (unsigned i = 0, size = resultInfo->getParameters().size();
           i < size; ++i) {
         require(resultInfo->getParameters()[i] ==
                 substTy->getParameters()[i],
                 "inputs to result function type do not match unapplied inputs "
                 "of original function");
      }

      require(resultInfo->getNumResults() == substTy->getNumResults(),
              "applied results do not agree in count with function type");
      for (unsigned i = 0, size = resultInfo->getNumResults(); i < size; ++i) {
         auto originalResult = resultInfo->getResults()[i];
         auto expectedResult = substTy->getResults()[i];

         // The "returns inner pointer" convention doesn't survive through a
         // partial application, since the thunk takes responsibility for
         // lifetime-extending 'self'.
         if (expectedResult.getConvention()
             == ResultConvention::UnownedInnerPointer) {
            expectedResult = PILResultInfo(
               expectedResult.getReturnValueType(F.getModule(), substTy),
               ResultConvention::Unowned);
            require(originalResult == expectedResult,
                    "result type of result function type for partially applied "
                    "@unowned_inner_pointer function should have @unowned"
                    "convention");

            // The "autoreleased" convention doesn't survive through a
            // partial application, since the thunk takes responsibility for
            // retaining the return value.
         } else if (expectedResult.getConvention()
                    == ResultConvention::Autoreleased) {
            expectedResult = PILResultInfo(
               expectedResult.getReturnValueType(F.getModule(), substTy),
               ResultConvention::Owned);
            require(originalResult == expectedResult,
                    "result type of result function type for partially applied "
                    "@autoreleased function should have @owned convention");

         } else {
            require(originalResult == expectedResult,
                    "result type of result function type does not match original "
                    "function");
         }
      }

      // TODO: Impose additional constraints when partial_apply when the
      // -disable-sil-partial-apply flag is enabled. We want to reduce
      // partial_apply to being only a means of associating a closure invocation
      // function with its context.
      //
      // When we reach that point, we should be able to more deeply redesign
      // PartialApplyInst to simplify the representation to carry a single
      // argument.
      if (PAI->getModule().getOptions().DisablePILPartialApply) {
         // Should only be one context argument.
         require(PAI->getArguments().size() == 1,
                 "partial_apply should have a single context argument");

         // Callee should already have the thin convention, and result should be
         // thick.
         require(resultInfo->getRepresentation() ==
                 PILFunctionTypeRepresentation::Thick,
                 "partial_apply result should have thick convention");
         require(PAI->getCallee()->getType().castTo<PILFunctionType>()
                    ->getRepresentation() ==
                 PILFunctionTypeRepresentation::Thin,
                 "partial_apply callee should have thin convention");

         // TODO: Check that generic signature matches box's generic signature,
         // once we have boxes with generic signatures.
         require(!PAI->getCalleeFunction()->getGenericEnvironment(),
                 "partial_apply context must capture generic environment for "
                 "callee");

         // Result's callee convention should match context argument's convention.
         require(substTy->getParameters().back().getConvention()
                 == resultInfo->getCalleeConvention(),
                 "partial_apply context argument must have the same convention "
                 "as the resulting function's callee convention");

         auto isPolarphpRefcounted = [](PILType t) -> bool {
            if (t.is<PILBoxType>())
               return true;
            if (t.getAstType() == t.getAstContext().TheNativeObjectType)
               return true;
            if (auto clas = t.getClassOrBoundGenericClass())
               // Must be a class defined in Swift.
               return clas->hasKnownPolarphpImplementation();
            return false;
         };

         // The context argument must be a swift-refcounted box or class.
         require(isPolarphpRefcounted(PAI->getArguments().front()->getType()),
                 "partial_apply context argument must be swift-refcounted");
      }
   }

   void checkBuiltinInst(BuiltinInst *BI) {
      // Check for special constraints on llvm intrinsics.
      if (BI->getIntrinsicInfo().ID != llvm::Intrinsic::not_intrinsic) {
         verifyLLVMIntrinsic(BI, BI->getIntrinsicInfo().ID);
         return;
      }
   }

   void checkFunctionRefBaseInst(FunctionRefBaseInst *FRI) {
      auto fnType = requireObjectType(PILFunctionType, FRI,
                                      "result of function_ref");
      require(!fnType->getExtInfo().hasContext(),
              "function_ref should have a context-free function result");

      // Note: in SingleFunction mode, we relax some of these checks because
      // we may not have linked everything yet.

      PILFunction *RefF = FRI->getInitiallyReferencedFunction();

      if (isa<FunctionRefInst>(FRI))
         require(
            !RefF->isDynamicallyReplaceable(),
            "function_ref cannot reference a [dynamically_replaceable] function");
      else if (isa<PreviousDynamicFunctionRefInst>(FRI)) {
         require(!RefF->isDynamicallyReplaceable(),
                 "previous_function_ref cannot reference a "
                 "[dynamically_replaceable] function");
         require(RefF->getDynamicallyReplacedFunction(),
                 "previous_function_ref must reference a "
                 "[dynamic_replacement_for:...] function");
      } else if (isa<DynamicFunctionRefInst>(FRI))
         require(RefF->isDynamicallyReplaceable(),
                 "dynamic_function_ref must reference a "
                 "[dynamically_replaceable] function");

      // In canonical PIL, direct reference to a shared_external declaration
      // is an error; we should have deserialized a body. In raw PIL, we may
      // not have deserialized the body yet.
      if (F.getModule().getStage() >= PILStage::Canonical) {
         if (RefF->isExternalDeclaration()) {
            require(SingleFunction ||
                    !hasSharedVisibility(RefF->getLinkage()) ||
                    RefF->hasForeignBody(),
                    "external declarations of PILFunctions with shared visibility is "
                    "not allowed");
         }
      }

      // A direct reference to a non-public or shared but not fragile function
      // from a fragile function is an error.
      if (F.isSerialized()) {
         require((SingleFunction && RefF->isExternalDeclaration()) ||
                 RefF->hasValidLinkageForFragileRef(),
                 "function_ref inside fragile function cannot "
                 "reference a private or hidden symbol");
      }

      verifyPILFunctionType(fnType);
   }

   void checkFunctionRefInst(FunctionRefInst *FRI) {
      checkFunctionRefBaseInst(FRI);
   }

   void checkDynamicFunctionRefInst(DynamicFunctionRefInst *FRI) {
      checkFunctionRefBaseInst(FRI);
   }

   void checkPreviousDynamicFunctionRefInst(PreviousDynamicFunctionRefInst *FRI) {
      checkFunctionRefBaseInst(FRI);
   }

   void checkAllocGlobalInst(AllocGlobalInst *AGI) {
      PILGlobalVariable *RefG = AGI->getReferencedGlobal();
      if (auto *VD = RefG->getDecl()) {
         require(!VD->isResilient(F.getModule().getPolarphpModule(),
                                  F.getResilienceExpansion()),
                 "cannot access storage of resilient global");
      }
      if (F.isSerialized()) {
         require(RefG->isSerialized()
                 || hasPublicVisibility(RefG->getLinkage()),
                 "alloc_global inside fragile function cannot "
                 "reference a private or hidden symbol");
      }
   }

   void checkGlobalAccessInst(GlobalAccessInst *GAI) {
      PILGlobalVariable *RefG = GAI->getReferencedGlobal();
      require(GAI->getType().getObjectType() ==
              RefG->getLoweredTypeInContext(F.getTypeExpansionContext()),
              "global_addr/value must be the type of the variable it references");
      if (auto *VD = RefG->getDecl()) {
         require(!VD->isResilient(F.getModule().getPolarphpModule(),
                                  F.getResilienceExpansion()),
                 "cannot access storage of resilient global");
      }
      if (F.isSerialized()) {
         require(RefG->isSerialized()
                 || hasPublicVisibility(RefG->getLinkage()),
                 "global_addr/value inside fragile function cannot "
                 "reference a private or hidden symbol");
      }
   }

   void checkGlobalAddrInst(GlobalAddrInst *GAI) {
      require(GAI->getType().isAddress(),
              "global_addr must have an address result type");
      require(!GAI->getReferencedGlobal()->isInitializedObject(),
              "global_addr cannot refer to a statically initialized object");
      checkGlobalAccessInst(GAI);
   }

   void checkGlobalValueInst(GlobalValueInst *GVI) {
      require(GVI->getType().isObject(),
              "global_value must have an address result type");
      checkGlobalAccessInst(GVI);
   }

   void checkObjectInst(ObjectInst *) {
      require(false, "object instruction is only allowed in a static initializer");
   }

   void checkIntegerLiteralInst(IntegerLiteralInst *ILI) {
      require(ILI->getType().is<AnyBuiltinIntegerType>(),
              "invalid integer literal type");
   }

   void checkLoadInst(LoadInst *LI) {
      require(LI->getType().isObject(), "Result of load must be an object");
      require(!fnConv.useLoweredAddresses()
              || LI->getType().isLoadable(*LI->getFunction()),
              "Load must have a loadable type");
      require(LI->getOperand()->getType().isAddress(),
              "Load operand must be an address");
      require(LI->getOperand()->getType().getObjectType() == LI->getType(),
              "Load operand type and result type mismatch");

      // Ownership semantic checks.
      switch (LI->getOwnershipQualifier()) {
         case LoadOwnershipQualifier::Unqualified:
            // We should not see loads with unqualified ownership when PILOwnership is
            // enabled.
            require(!F.hasOwnership(),
                    "Load with unqualified ownership in a qualified function");
            break;
         case LoadOwnershipQualifier::Copy:
         case LoadOwnershipQualifier::Take:
            require(F.hasOwnership(),
                    "Load with qualified ownership in an unqualified function");
            // TODO: Could probably make this a bit stricter.
            require(!LI->getType().isTrivial(*LI->getFunction()),
                    "load [copy] or load [take] can only be applied to non-trivial "
                    "types");
            break;
         case LoadOwnershipQualifier::Trivial:
            require(F.hasOwnership(),
                    "Load with qualified ownership in an unqualified function");
            require(LI->getType().isTrivial(*LI->getFunction()),
                    "A load with trivial ownership must load a trivial type");
            break;
      }
   }

   void checkLoadBorrowInst(LoadBorrowInst *LBI) {
      require(
         F.hasOwnership(),
         "Inst with qualified ownership in a function that is not qualified");
      require(LBI->getType().isObject(), "Result of load must be an object");
      require(!fnConv.useLoweredAddresses()
              || LBI->getType().isLoadable(*LBI->getFunction()),
              "Load must have a loadable type");
      require(LBI->getOperand()->getType().isAddress(),
              "Load operand must be an address");
      require(LBI->getOperand()->getType().getObjectType() == LBI->getType(),
              "Load operand type and result type mismatch");
   }

   void checkEndBorrowInst(EndBorrowInst *EBI) {
      require(
         F.hasOwnership(),
         "Inst with qualified ownership in a function that is not qualified");
   }

   template <class AI>
   void checkAccessEnforcement(AI *AccessInst) {
      if (AccessInst->getModule().getStage() != PILStage::Raw) {
         require(AccessInst->getEnforcement() != PILAccessEnforcement::Unknown,
                 "access must have known enforcement outside raw stage");
      }
   }

   void checkBeginAccessInst(BeginAccessInst *BAI) {
      requireSameType(BAI->getType(), BAI->getSource()->getType(),
                      "result must be same type as operand");
      require(BAI->getType().isAddress(),
              "begin_access operand must have address type");

      checkAccessEnforcement(BAI);

      switch (BAI->getAccessKind()) {
         case PILAccessKind::Init:
         case PILAccessKind::Deinit:
            require(BAI->getEnforcement() == PILAccessEnforcement::Static,
                    "init/deinit accesses cannot use non-static enforcement");
            break;

         case PILAccessKind::Read:
         case PILAccessKind::Modify:
            break;
      }

      // Verify that all formal accesses patterns are recognized as part of a
      // whitelist. The presence of an unknown pattern means that analysis will
      // silently fail, and the compiler may be introducing undefined behavior
      // with no other way to detect it.
      //
      // For example, AccessEnforcementWMO runs very late in the
      // pipeline and assumes valid storage for all dynamic Read/Modify access. It
      // also requires that Unidentified access fit a whitelist on known
      // non-internal globals or class properties.
      //
      // First check that findAccessedStorage returns without asserting. For
      // Unsafe enforcement, that is sufficient. For any other enforcement
      // level also require that it returns a valid AccessedStorage object.
      // Unsafe enforcement is used for some unrecognizable access patterns,
      // like debugger variables. The compiler never cares about the source of
      // those accesses.
      findAccessedStorage(BAI->getSource());
      // FIXME: rdar://57291811 - the following check for valid storage will be
      // reenabled shortly. A fix is planned. In the meantime, the possiblity that
      // a real miscompilation could be caused by this failure is insignificant.
      // I will probably enable a much broader PILVerification of address-type
      // block arguments first to ensure we never hit this check again.
      /*
    AccessedStorage storage = findAccessedStorage(BAI->getSource());
    if (BAI->getEnforcement() != PILAccessEnforcement::Unsafe)
      require(storage, "Unknown formal access pattern");
    */
   }

   void checkEndAccessInst(EndAccessInst *EAI) {
      auto BAI = dyn_cast<BeginAccessInst>(EAI->getOperand());
      require(BAI != nullptr,
              "operand of end_access must be a begin_access");

      if (EAI->isAborting()) {
         require(BAI->getAccessKind() == PILAccessKind::Init ||
                 BAI->getAccessKind() == PILAccessKind::Deinit,
                 "aborting access must apply to init or deinit");
      }
   }

   void checkBeginUnpairedAccessInst(BeginUnpairedAccessInst *BUAI) {
      require(BUAI->getEnforcement() != PILAccessEnforcement::Unknown,
              "unpaired access can never use unknown enforcement");
      require(BUAI->getSource()->getType().isAddress(),
              "address operand must have address type");
      requireAddressType(BuiltinUnsafeValueBufferType, BUAI->getBuffer(),
                         "scratch buffer operand");

      checkAccessEnforcement(BUAI);

      switch (BUAI->getAccessKind()) {
         case PILAccessKind::Init:
         case PILAccessKind::Deinit:
            require(BUAI->getEnforcement() == PILAccessEnforcement::Static,
                    "init/deinit accesses cannot use non-static enforcement");
            break;
         case PILAccessKind::Read:
         case PILAccessKind::Modify:
            break;
      }

      // First check that findAccessedStorage never asserts.
      AccessedStorage storage = findAccessedStorage(BUAI->getSource());
      // Only allow Unsafe and Builtin access to have invalid storage.
      if (BUAI->getEnforcement() != PILAccessEnforcement::Unsafe
          && !BUAI->isFromBuiltin()) {
         require(storage, "Unknown formal access pattern");
      }
   }

   void checkEndUnpairedAccessInst(EndUnpairedAccessInst *I) {
      require(I->getEnforcement() != PILAccessEnforcement::Unknown,
              "unpaired access can never use unknown enforcement");
      requireAddressType(BuiltinUnsafeValueBufferType, I->getBuffer(),
                         "scratch buffer operand");

      checkAccessEnforcement(I);
   }

   void checkStoreInst(StoreInst *SI) {
      require(SI->getSrc()->getType().isObject(),
              "Can't store from an address source");
      require(!fnConv.useLoweredAddresses()
              || SI->getSrc()->getType().isLoadable(*SI->getFunction()),
              "Can't store a non loadable type");
      require(SI->getDest()->getType().isAddress(),
              "Must store to an address dest");
      require(SI->getDest()->getType().getObjectType() == SI->getSrc()->getType(),
              "Store operand type and dest type mismatch");

      // Perform ownership checks.
      switch (SI->getOwnershipQualifier()) {
         case StoreOwnershipQualifier::Unqualified:
            // We should not see loads with unqualified ownership when PILOwnership is
            // enabled.
            require(!F.hasOwnership(),
                    "Qualified store in function with unqualified ownership?!");
            break;
         case StoreOwnershipQualifier::Init:
         case StoreOwnershipQualifier::Assign:
            require(
               F.hasOwnership(),
               "Inst with qualified ownership in a function that is not qualified");
            // TODO: Could probably make this a bit stricter.
            require(!SI->getSrc()->getType().isTrivial(*SI->getFunction()),
                    "store [init] or store [assign] can only be applied to "
                    "non-trivial types");
            break;
         case StoreOwnershipQualifier::Trivial: {
            require(
               F.hasOwnership(),
               "Inst with qualified ownership in a function that is not qualified");
            PILValue Src = SI->getSrc();
            require(Src->getType().isTrivial(*SI->getFunction()) ||
                    Src.getOwnershipKind() == ValueOwnershipKind::None,
                    "A store with trivial ownership must store a type with trivial "
                    "ownership");
            break;
         }
      }
   }

   void checkAssignInst(AssignInst *AI) {
      PILValue Src = AI->getSrc(), Dest = AI->getDest();
      require(AI->getModule().getStage() == PILStage::Raw,
              "assign instruction can only exist in raw PIL");
      require(Src->getType().isObject(), "Can't assign from an address source");
      require(Dest->getType().isAddress(), "Must store to an address dest");
      require(Dest->getType().getObjectType() == Src->getType(),
              "Store operand type and dest type mismatch");
   }

   // Usually the assign_by_wrapper initializer or setter has a single argument
   // (the value). But in case of a tuple, the initializer/setter expect the
   // tuple elements as separate arguments.
   void checkAssignByWrapperArgsRecursively(PILType ty,
                                            PILFunctionConventions &conv, unsigned &argIdx) {
      if (auto tupleTy = ty.getAs<TupleType>()) {
         for (Type et : tupleTy->getElementTypes()) {
            PILType elTy = PILType::getPrimitiveType(CanType(et), ty.getCategory());
            checkAssignByWrapperArgsRecursively(elTy, conv, argIdx);
         }
         return;
      }
      require(argIdx < conv.getNumPILArguments(),
              "initializer or setter has too few arguments");
      PILType argTy = conv.getPILArgumentType(argIdx++);
      if (ty.isAddress() && argTy.isObject())
         ty = ty.getObjectType();
      require(ty == argTy,
              "wrong argument type of initializer or setter");
   }

   void checkAssignByWrapperArgs(PILType ty, PILFunctionConventions &conv) {
      unsigned argIdx = conv.getPILArgIndexOfFirstParam();
      checkAssignByWrapperArgsRecursively(ty, conv, argIdx);
      require(argIdx == conv.getNumPILArguments(),
              "initializer or setter has too many arguments");
   }

   void checkAssignByWrapperInst(AssignByWrapperInst *AI) {
      PILValue Src = AI->getSrc(), Dest = AI->getDest();
      require(AI->getModule().getStage() == PILStage::Raw,
              "assign instruction can only exist in raw PIL");
      require(Dest->getType().isAddress(), "Must store to an address dest");

      PILValue initFn = AI->getInitializer();
      CanPILFunctionType initTy = initFn->getType().castTo<PILFunctionType>();
      PILFunctionConventions initConv(initTy, AI->getModule());
      checkAssignByWrapperArgs(Src->getType(), initConv);
      switch (initConv.getNumIndirectPILResults()) {
         case 0:
            require(initConv.getNumDirectPILResults() == 1,
                    "wrong number of init function results");
            require(Dest->getType().getObjectType() ==
                    *initConv.getDirectPILResultTypes().begin(),
                    "wrong init function result type");
            break;
         case 1:
            require(initConv.getNumDirectPILResults() == 0,
                    "wrong number of init function results");
            require(Dest->getType() ==
                    *initConv.getIndirectPILResultTypes().begin(),
                    "wrong indirect init function result type");
            break;
         default:
            require(false, "wrong number of indirect init function results");
      }

      PILValue setterFn = AI->getSetter();
      CanPILFunctionType setterTy = setterFn->getType().castTo<PILFunctionType>();
      PILFunctionConventions setterConv(setterTy, AI->getModule());
      require(setterConv.getNumIndirectPILResults() == 0,
              "set function has indirect results");
      checkAssignByWrapperArgs(Src->getType(), setterConv);
   }

#define NEVER_LOADABLE_CHECKED_REF_STORAGE(Name, name, ...) \
  void checkLoad##Name##Inst(Load##Name##Inst *LWI) { \
    require(LWI->getType().isObject(), "Result of load must be an object"); \
    auto isOptional = bool(LWI->getType().getOptionalObjectType()); \
    auto optionality = optionalityOf(ReferenceOwnership::Name); \
    if (optionality == ReferenceOwnershipOptionality::Required) \
      require(isOptional, "Optionality mismatch"); \
    if (optionality == ReferenceOwnershipOptionality::Disallowed) \
      require(!isOptional, "Optionality mismatch"); \
    auto PointerType = LWI->getOperand()->getType(); \
    auto PointerRVType = PointerType.getAstType(); \
    require(PointerType.isAddress() && \
            PointerRVType->is<Name##StorageType>(), \
            "load_" #name " operand must be a " #name " address"); \
    require(PointerRVType->getReferenceStorageReferent()->getCanonicalType() ==\
            LWI->getType().getAstType(), \
            "Load operand type and result type mismatch"); \
  } \
  void checkStore##Name##Inst(Store##Name##Inst *SWI) { \
    auto SrcTy = SWI->getSrc()->getType(); \
    require(SrcTy.isObject(), "Can't store from an address source"); \
    auto isOptional = bool(SrcTy.getOptionalObjectType()); \
    auto optionality = optionalityOf(ReferenceOwnership::Name); \
    if (optionality == ReferenceOwnershipOptionality::Required) \
      require(isOptional, "Optionality mismatch"); \
    if (optionality == ReferenceOwnershipOptionality::Disallowed) \
      require(!isOptional, "Optionality mismatch"); \
    auto PointerType = SWI->getDest()->getType(); \
    auto PointerRVType = PointerType.getAstType(); \
    require(PointerType.isAddress() && \
            PointerRVType->is<Name##StorageType>(), \
            "store_" #name " address operand must be a " #name " address"); \
    require(PointerRVType->getReferenceStorageReferent()->getCanonicalType() ==\
            SrcTy.getAstType(), \
            "Store operand type and dest type mismatch"); \
  }
#define LOADABLE_REF_STORAGE_HELPER(Name, name) \
  void checkRefTo##Name##Inst(RefTo##Name##Inst *I) { \
    requireReferenceStorageCapableValue(I->getOperand(), \
                                        "Operand of ref_to_" #name); \
    auto operandType = I->getOperand()->getType().getAstType(); \
    auto resultType = requireObjectType(Name##StorageType, I, \
                                        "Result of ref_to_" #name); \
    require(resultType.getReferentType() == operandType, \
            "Result of ref_to_" #name " does not have the " \
            "operand's type as its referent type"); \
  } \
  void check##Name##ToRefInst(Name##ToRefInst *I) { \
    auto operandType = requireObjectType(Name##StorageType, \
                                         I->getOperand(), \
                                         "Operand of " #name "_to_ref"); \
    requireReferenceStorageCapableValue(I, "Result of " #name "_to_ref"); \
    auto resultType = I->getType().getAstType(); \
    require(operandType.getReferentType() == resultType, \
            "Operand of " #name "_to_ref does not have the " \
            "operand's type as its referent type"); \
  }
#define ALWAYS_LOADABLE_CHECKED_REF_STORAGE_HELPER(Name, name, closure)        \
  void checkStrongRetain##Name##Inst(StrongRetain##Name##Inst *RI) {           \
    auto ty = requireObjectType(Name##StorageType, RI->getOperand(),           \
                                "Operand of strong_retain_" #name);            \
    closure();                                                                 \
    (void)ty;                                                                  \
    require(!F.hasOwnership(), "strong_retain_" #name " is only in "           \
                               "functions with unqualified "                   \
                               "ownership");                                   \
  }                                                                            \
  void check##Name##RetainInst(Name##RetainInst *RI) {                         \
    auto ty = requireObjectType(Name##StorageType, RI->getOperand(),           \
                                "Operand of " #name "_retain");                \
    closure();                                                                 \
    (void)ty;                                                                  \
    require(!F.hasOwnership(),                                                 \
            #name "_retain is only in functions with unqualified ownership");  \
  }                                                                            \
  void check##Name##ReleaseInst(Name##ReleaseInst *RI) {                       \
    auto ty = requireObjectType(Name##StorageType, RI->getOperand(),           \
                                "Operand of " #name "_release");               \
    closure();                                                                 \
    (void)ty;                                                                  \
    require(!F.hasOwnership(),                                                 \
            #name "_release is only in functions with unqualified ownership"); \
  }                                                                            \
  void StrongcheckCopy##Name##ValueInst(StrongCopy##Name##ValueInst *I) {      \
    auto ty = requireObjectType(Name##StorageType, I->getOperand(),            \
                                "Operand of " #name "_retain");                \
    closure();                                                                 \
    (void)ty;                                                                  \
    /* *NOTE* We allow copy_##name##_value to be used throughout the entire */ \
    /* pipeline even though it is a higher level instruction. */               \
  }

#define ALWAYS_LOADABLE_CHECKED_REF_STORAGE(Name, name, ...) \
  LOADABLE_REF_STORAGE_HELPER(Name, name) \
  ALWAYS_LOADABLE_CHECKED_REF_STORAGE_HELPER(Name, name, []{})
#define SOMETIMES_LOADABLE_CHECKED_REF_STORAGE(Name, name, ...) \
  LOADABLE_REF_STORAGE_HELPER(Name, name) \
  NEVER_LOADABLE_CHECKED_REF_STORAGE(Name, name, "...") \
  ALWAYS_LOADABLE_CHECKED_REF_STORAGE_HELPER(Name, name, [&]{ \
    require(ty->isLoadable(ResilienceExpansion::Maximal), \
            "'" #name "' type must be loadable"); \
  })
#define UNCHECKED_REF_STORAGE(Name, name, ...)                                 \
  LOADABLE_REF_STORAGE_HELPER(Name, name)                                      \
  void checkStrongCopy##Name##ValueInst(StrongCopy##Name##ValueInst *I) {      \
    auto ty = requireObjectType(Name##StorageType, I->getOperand(),            \
                                "Operand of " #name "_retain");                \
    (void)ty;                                                                  \
    /* *NOTE* We allow copy_##name##_value to be used throughout the entire */ \
    /* pipeline even though it is a higher level instruction. */               \
  }

#include "polarphp/ast/ReferenceStorageDef.h"
#undef LOADABLE_REF_STORAGE_HELPER
#undef ALWAYS_LOADABLE_CHECKED_REF_STORAGE_HELPER

   void checkMarkUninitializedInst(MarkUninitializedInst *MU) {
      PILValue Src = MU->getOperand();
      require(MU->getModule().getStage() == PILStage::Raw,
              "mark_uninitialized instruction can only exist in raw PIL");
      require(Src->getType().isAddress() ||
              Src->getType().getClassOrBoundGenericClass() ||
              Src->getType().getAs<PILBoxType>(),
              "mark_uninitialized must be an address, class, or box type");
      require(Src->getType() == MU->getType(),"operand and result type mismatch");
      // FIXME: When the work to force MUI to be on Allocations/PILArguments
      // complete, turn on this assertion.
      require(isa<AllocationInst>(Src)
              || isa<GlobalAddrInst>(Src)
              // TODO: Should we support PILUndef on mark_uninitialized? We
              // currently have a test that verifies this behavior, but it seems
              // like this would always be a bug due to the implications around
              // the code in DI. This just bakes in the current behavior.
              || isa<PILUndef>(Src)
              // We allow PILArguments to support the case of initializing
              // initializers. In such a case, the underlying case is allocated
              // outside by the allocating initializer and we pass in the to be
              // initialized value as a PILArgument.
              || isa<PILArgument>(Src)
              // FIXME: Once the MarkUninitializedFixup pass is eliminated,
              // mark_uninitialized should never be applied to a project_box. So
              // at that point, this should be eliminated.
              || isa<ProjectBoxInst>(Src)
              // FIXME: We only support pointer to address here to not break LLDB. It is
              // important that long term we get rid of this since this is a situation
              // where LLDB is breaking PILGen/DI invariants by not creating a new
              // independent stack location for the pointer to address.
              || isa<PointerToAddressInst>(Src),
              "Mark Uninitialized must be applied to a storage location");
   }

   void checkMarkFunctionEscapeInst(MarkFunctionEscapeInst *MFE) {
      require(MFE->getModule().getStage() == PILStage::Raw,
              "mark_function_escape instruction can only exist in raw PIL");
      for (auto Elt : MFE->getElements())
         require(Elt->getType().isAddress(), "MFE must refer to variable addrs");
   }

   void checkCopyAddrInst(CopyAddrInst *SI) {
      require(SI->getSrc()->getType().isAddress(),
              "Src value should be lvalue");
      require(SI->getDest()->getType().isAddress(),
              "Dest address should be lvalue");
      require(SI->getDest()->getType() == SI->getSrc()->getType(),
              "Store operand type and dest type mismatch");
      require(F.isTypeABIAccessible(SI->getDest()->getType()),
              "cannot directly copy type with inaccessible ABI");
   }

   void checkRetainValueInst(RetainValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(!F.hasOwnership(),
              "retain_value is only in functions with unqualified ownership");
   }

   void checkRetainValueAddrInst(RetainValueAddrInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Source value should be an address value");
      require(!F.hasOwnership(),
              "retain_value is only in functions with unqualified ownership");
   }

   void checkCopyValueInst(CopyValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(!I->getOperand()->getType().isTrivial(*I->getFunction()),
              "Source value should be non-trivial");
      require(!fnConv.useLoweredAddresses() || F.hasOwnership(),
              "copy_value is only valid in functions with qualified "
              "ownership");
   }

   void checkDestroyValueInst(DestroyValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(!I->getOperand()->getType().isTrivial(*I->getFunction()),
              "Source value should be non-trivial");
      require(!fnConv.useLoweredAddresses() || F.hasOwnership(),
              "destroy_value is only valid in functions with qualified "
              "ownership");
   }

   void checkReleaseValueInst(ReleaseValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(!F.hasOwnership(),
              "release_value is only in functions with unqualified ownership");
   }

   void checkReleaseValueAddrInst(ReleaseValueAddrInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Source value should be an address value");
      require(!F.hasOwnership(),
              "release_value is only in functions with unqualified ownership");
   }

   void checkAutoreleaseValueInst(AutoreleaseValueInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      // TODO: This instruction could in principle be generalized.
      require(I->getOperand()->getType().hasRetainablePointerRepresentation(),
              "Source value must be a reference type or optional thereof");
   }

   void checkSetDeallocatingInst(SetDeallocatingInst *I) {
      require(I->getOperand()->getType().isObject(),
              "Source value should be an object value");
      require(I->getOperand()->getType().hasRetainablePointerRepresentation(),
              "Source value must be a reference type");
   }

   void checkCopyBlockInst(CopyBlockInst *I) {
      require(I->getOperand()->getType().isBlockPointerCompatible(),
              "operand of copy_block should be a block");
      require(I->getOperand()->getType() == I->getType(),
              "result of copy_block should be same type as operand");
   }
   void checkCopyBlockInst(CopyBlockWithoutEscapingInst *I) {
      require(I->getBlock()->getType().isBlockPointerCompatible(),
              "operand of copy_block should be a block");
      require(I->getBlock()->getType() == I->getType(),
              "result of copy_block should be same type as operand");
      auto FnTy = requireObjectType(PILFunctionType, I->getClosure(),
                                    "copy_block_without_escaping operand");
      require(!FnTy->isNoEscape(),
              "closure parameter must not be a @noescape closure");
   }

   void checkAllocValueBufferInst(AllocValueBufferInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Operand value should be an address");
      require(I->getOperand()->getType().is<BuiltinUnsafeValueBufferType>(),
              "Operand value should be a Builtin.UnsafeValueBuffer");
      verifyOpenedArchetype(I, I->getValueType().getAstType());
   }

   void checkProjectValueBufferInst(ProjectValueBufferInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Operand value should be an address");
      require(I->getOperand()->getType().is<BuiltinUnsafeValueBufferType>(),
              "Operand value should be a Builtin.UnsafeValueBuffer");
   }

   void checkProjectBoxInst(ProjectBoxInst *I) {
      require(I->getOperand()->getType().isObject(),
              "project_box operand should be a value");
      auto boxTy = I->getOperand()->getType().getAs<PILBoxType>();
      require(boxTy, "project_box operand should be a @box type");
      require(I->getType() == getPILBoxFieldType(F.getTypeExpansionContext(), boxTy,
                                                 F.getModule().Types,
                                                 I->getFieldIndex()),
              "project_box result should be address of boxed type");

      // If we have a mark_uninitialized as a user, the mark_uninitialized must be
      // our only user. This is a requirement that is asserted by allocbox to
      // stack. This check just embeds the requirement into the IR.
      require(I->hasOneUse() ||
              none_of(I->getUses(),
                      [](Operand *Op) -> bool {
                         return isa<MarkUninitializedInst>(Op->getUser());
                      }),
              "project_box with more than one user when a user is a "
              "mark_uninitialized");
   }

   void checkProjectExistentialBoxInst(ProjectExistentialBoxInst *PEBI) {
      PILType operandType = PEBI->getOperand()->getType();
      require(operandType.isObject(),
              "project_existential_box operand must not be address");

      require(operandType.canUseExistentialRepresentation(
         ExistentialRepresentation::Boxed),
              "project_existential_box operand must be boxed existential");

      require(PEBI->getType().isAddress(),
              "project_existential_box result must be an address");

      if (auto *AEBI = dyn_cast<AllocExistentialBoxInst>(PEBI->getOperand())) {
         // The lowered type must be the properly-abstracted form of the AST type.
         PILType exType = AEBI->getExistentialType();
         auto archetype = OpenedArchetypeType::get(exType.getAstType());

         auto loweredTy = F.getLoweredType(lowering::AbstractionPattern(archetype),
                                           AEBI->getFormalConcreteType())
            .getAddressType();

         requireSameType(loweredTy, PEBI->getType(),
                         "project_existential_box result should be the lowered "
                         "concrete type of its alloc_existential_box");
      }
   }

   void checkDeallocValueBufferInst(DeallocValueBufferInst *I) {
      require(I->getOperand()->getType().isAddress(),
              "Operand value should be an address");
      require(I->getOperand()->getType().is<BuiltinUnsafeValueBufferType>(),
              "Operand value should be a Builtin.UnsafeValueBuffer");
   }

   void checkStructInst(StructInst *SI) {
      auto *structDecl = SI->getType().getStructOrBoundGenericStruct();
      require(structDecl, "StructInst must return a struct");
      require(!structDecl->hasUnreferenceableStorage(),
              "Cannot build a struct with unreferenceable storage from elements "
              "using StructInst");
      require(!structDecl->isResilient(F.getModule().getPolarphpModule(),
                                       F.getResilienceExpansion()),
              "cannot access storage of resilient struct");
      require(SI->getType().isObject(),
              "StructInst must produce an object");

      PILType structTy = SI->getType();
      auto opi = SI->getElements().begin(), opEnd = SI->getElements().end();
      for (VarDecl *field : structDecl->getStoredProperties()) {
         require(opi != opEnd,
                 "number of struct operands does not match number of stored "
                 "member variables of struct");

         PILType loweredType =
            structTy.getFieldType(field, F.getModule(), F.getTypeExpansionContext());
         if (SI->getModule().getStage() != PILStage::Lowered) {
            require((*opi)->getType() == loweredType,
                    "struct operand type does not match field type");
         }
         ++opi;
      }
   }

   void checkEnumInst(EnumInst *UI) {
      EnumDecl *ud = UI->getType().getEnumOrBoundGenericEnum();
      require(ud, "EnumInst must return an enum");
      require(UI->getElement()->getParentEnum() == ud,
              "EnumInst case must be a case of the result enum type");
      require(UI->getType().isObject(),
              "EnumInst must produce an object");
      require(UI->hasOperand() == UI->getElement()->hasAssociatedValues(),
              "EnumInst must take an argument iff the element does");

      if (UI->getElement()->hasAssociatedValues()) {
         require(UI->getOperand()->getType().isObject(),
                 "EnumInst operand must be an object");
         PILType caseTy = UI->getType().getEnumElementType(
            UI->getElement(), F.getModule(), F.getTypeExpansionContext());
         if (UI->getModule().getStage() != PILStage::Lowered) {
            require(caseTy == UI->getOperand()->getType(),
                    "EnumInst operand type does not match type of case");
         }
      }
   }

   void checkInitEnumDataAddrInst(InitEnumDataAddrInst *UI) {
      EnumDecl *ud = UI->getOperand()->getType().getEnumOrBoundGenericEnum();
      require(ud, "InitEnumDataAddrInst must take an enum operand");
      require(UI->getElement()->getParentEnum() == ud,
              "InitEnumDataAddrInst case must be a case of the enum operand type");
      require(UI->getElement()->hasAssociatedValues(),
              "InitEnumDataAddrInst case must have a data type");
      require(UI->getOperand()->getType().isAddress(),
              "InitEnumDataAddrInst must take an address operand");
      require(UI->getType().isAddress(),
              "InitEnumDataAddrInst must produce an address");

      PILType caseTy = UI->getOperand()->getType().getEnumElementType(
         UI->getElement(), F.getModule(), F.getTypeExpansionContext());

      if (UI->getModule().getStage() != PILStage::Lowered) {
         requireSameType(
            caseTy, UI->getType(),
            "InitEnumDataAddrInst result does not match type of enum case");
      }
   }

   void checkUncheckedEnumDataInst(UncheckedEnumDataInst *UI) {
      EnumDecl *ud = UI->getOperand()->getType().getEnumOrBoundGenericEnum();
      require(ud, "UncheckedEnumData must take an enum operand");
      require(UI->getElement()->getParentEnum() == ud,
              "UncheckedEnumData case must be a case of the enum operand type");
      require(UI->getElement()->getArgumentInterfaceType(),
              "UncheckedEnumData case must have a data type");
      require(UI->getOperand()->getType().isObject(),
              "UncheckedEnumData must take an address operand");
      require(UI->getType().isObject(),
              "UncheckedEnumData must produce an address");

      PILType caseTy = UI->getOperand()->getType().getEnumElementType(
         UI->getElement(), F.getModule(), F.getTypeExpansionContext());

      if (UI->getModule().getStage() != PILStage::Lowered) {
         require(caseTy == UI->getType(),
                 "UncheckedEnumData result does not match type of enum case");
      }
   }

   void checkUncheckedTakeEnumDataAddrInst(UncheckedTakeEnumDataAddrInst *UI) {
      EnumDecl *ud = UI->getOperand()->getType().getEnumOrBoundGenericEnum();
      require(ud, "UncheckedTakeEnumDataAddrInst must take an enum operand");
      require(UI->getElement()->getParentEnum() == ud,
              "UncheckedTakeEnumDataAddrInst case must be a case of the enum operand type");
      require(UI->getElement()->getArgumentInterfaceType(),
              "UncheckedTakeEnumDataAddrInst case must have a data type");
      require(UI->getOperand()->getType().isAddress(),
              "UncheckedTakeEnumDataAddrInst must take an address operand");
      require(UI->getType().isAddress(),
              "UncheckedTakeEnumDataAddrInst must produce an address");

      PILType caseTy = UI->getOperand()->getType().getEnumElementType(
         UI->getElement(), F.getModule(), F.getTypeExpansionContext());

      if (UI->getModule().getStage() != PILStage::Lowered) {
         require(caseTy == UI->getType(), "UncheckedTakeEnumDataAddrInst result "
                                          "does not match type of enum case");
      }
   }

   void checkInjectEnumAddrInst(InjectEnumAddrInst *IUAI) {
      require(IUAI->getOperand()->getType().is<EnumType>()
              || IUAI->getOperand()->getType().is<BoundGenericEnumType>(),
              "InjectEnumAddrInst must take an enum operand");
      require(IUAI->getElement()->getParentEnum()
              == IUAI->getOperand()->getType().getEnumOrBoundGenericEnum(),
              "InjectEnumAddrInst case must be a case of the enum operand type");
      require(IUAI->getOperand()->getType().isAddress(),
              "InjectEnumAddrInst must take an address operand");
   }

   void checkTupleInst(TupleInst *TI) {
      CanTupleType ResTy = requireObjectType(TupleType, TI, "Result of tuple");

      require(TI->getElements().size() == ResTy->getNumElements(),
              "Tuple field count mismatch!");

      if (TI->getModule().getStage() != PILStage::Lowered) {
         for (size_t i = 0, size = TI->getElements().size(); i < size; ++i) {
            require(TI->getElement(i)->getType().getAstType() ==
                    ResTy.getElementType(i),
                    "Tuple element arguments do not match tuple type!");
         }
      }
   }

   // Is a PIL type a potential lowering of a formal type?
   bool isLoweringOf(PILType loweredType, CanType formalType) {
      return loweredType.isLoweringOf(F.getTypeExpansionContext(), F.getModule(),
                                      formalType);
   }

   void checkMetatypeInst(MetatypeInst *MI) {
      require(MI->getType().is<MetatypeType>(),
              "metatype instruction must be of metatype type");
      auto MetaTy = MI->getType().castTo<MetatypeType>();
      require(MetaTy->hasRepresentation(),
              "metatype instruction must have a metatype representation");
      verifyOpenedArchetype(MI, MetaTy.getInstanceType());
   }
   void checkValueMetatypeInst(ValueMetatypeInst *MI) {
      require(MI->getType().is<MetatypeType>(),
              "value_metatype instruction must be of metatype type");
      require(MI->getType().castTo<MetatypeType>()->hasRepresentation(),
              "value_metatype instruction must have a metatype representation");
      auto formalInstanceTy
         = MI->getType().castTo<MetatypeType>().getInstanceType();
      require(isLoweringOf(MI->getOperand()->getType(), formalInstanceTy),
              "value_metatype result must be formal metatype of "
              "lowered operand type");
   }
   void checkExistentialMetatypeInst(ExistentialMetatypeInst *MI) {
      require(MI->getType().is<ExistentialMetatypeType>(),
              "existential_metatype instruction must be of metatype type");
      require(MI->getType().castTo<ExistentialMetatypeType>()->hasRepresentation(),
              "value_metatype instruction must have a metatype representation");
      require(MI->getOperand()->getType().isAnyExistentialType(),
              "existential_metatype operand must be of protocol type");
      auto formalInstanceTy
         = MI->getType().castTo<ExistentialMetatypeType>().getInstanceType();
      require(isLoweringOf(MI->getOperand()->getType(), formalInstanceTy),
              "existential_metatype result must be formal metatype of "
              "lowered operand type");
   }

   void checkStrongRetainInst(StrongRetainInst *RI) {
      requireReferenceValue(RI->getOperand(), "Operand of strong_retain");
      require(!F.hasOwnership(),
              "strong_retain is only in functions with unqualified ownership");
   }
   void checkStrongReleaseInst(StrongReleaseInst *RI) {
      requireReferenceValue(RI->getOperand(), "Operand of release");
      require(!F.hasOwnership(),
              "strong_release is only in functions with unqualified ownership");
   }

   void checkDeallocStackInst(DeallocStackInst *DI) {
      require(isa<PILUndef>(DI->getOperand()) ||
              isa<AllocStackInst>(DI->getOperand()) ||
              (isa<PartialApplyInst>(DI->getOperand()) &&
               cast<PartialApplyInst>(DI->getOperand())->isOnStack()),
              "Operand of dealloc_stack must be an alloc_stack or partial_apply "
              "[stack]");
   }
   void checkDeallocRefInst(DeallocRefInst *DI) {
      require(DI->getOperand()->getType().isObject(),
              "Operand of dealloc_ref must be object");
      auto *cd = DI->getOperand()->getType().getClassOrBoundGenericClass();
      require(cd, "Operand of dealloc_ref must be of class type");

      if (!DI->canAllocOnStack()) {
         require(!cd->isResilient(F.getModule().getPolarphpModule(),
                                  F.getResilienceExpansion()),
                 "cannot directly deallocate resilient class");
      }
   }
   void checkDeallocPartialRefInst(DeallocPartialRefInst *DPRI) {
      require(DPRI->getInstance()->getType().isObject(),
              "First operand of dealloc_partial_ref must be object");
      auto class1 = DPRI->getInstance()->getType().getClassOrBoundGenericClass();
      require(class1,
              "First operand of dealloc_partial_ref must be of class type");
      require(DPRI->getMetatype()->getType().is<MetatypeType>(),
              "Second operand of dealloc_partial_ref must be a metatype");
      auto class2 = DPRI->getMetatype()->getType().castTo<MetatypeType>()
         ->getInstanceType()->getClassOrBoundGenericClass();
      require(class2,
              "Second operand of dealloc_partial_ref must be a class metatype");
      require(class2->isSuperclassOf(class1),
              "First operand not superclass of second instance type");
   }

   void checkAllocBoxInst(AllocBoxInst *AI) {
      auto boxTy = AI->getType().getAs<PILBoxType>();
      require(boxTy, "alloc_box must have a @box type");

      require(AI->getType().isObject(),
              "result of alloc_box must be an object");
      for (unsigned field : indices(AI->getBoxType()->getLayout()->getFields())) {
         verifyOpenedArchetype(AI, getPILBoxFieldLoweredType(
            F.getTypeExpansionContext(), AI->getBoxType(),
            F.getModule().Types, field));
      }

      // An alloc_box with a mark_uninitialized user can not have any other users.
      require(none_of(AI->getUses(),
                      [](Operand *Op) -> bool {
                         return isa<MarkUninitializedInst>(Op->getUser());
                      }) ||
              AI->hasOneUse(),
              "An alloc_box with a mark_uninitialized user can not have any "
              "other users.");
   }

   void checkDeallocBoxInst(DeallocBoxInst *DI) {
      auto boxTy = DI->getOperand()->getType().getAs<PILBoxType>();
      require(boxTy, "operand must be a @box type");
      require(DI->getOperand()->getType().isObject(),
              "operand must be an object");
   }

   void checkDestroyAddrInst(DestroyAddrInst *DI) {
      require(DI->getOperand()->getType().isAddress(),
              "Operand of destroy_addr must be address");
      require(F.isTypeABIAccessible(DI->getOperand()->getType()),
              "cannot directly destroy type with inaccessible ABI");
   }

   void checkBindMemoryInst(BindMemoryInst *BI) {
      require(BI->getBoundType(), "BI must have a bound type");
      require(BI->getBase()->getType().is<BuiltinRawPointerType>(),
              "bind_memory base be a RawPointer");
      require(BI->getIndex()->getType()
              == PILType::getBuiltinWordType(F.getAstContext()),
              "bind_memory index must be a Word");
   }

   void checkIndexAddrInst(IndexAddrInst *IAI) {
      require(IAI->getType().isAddress(), "index_addr must produce an address");
      require(IAI->getType() == IAI->getBase()->getType(),
              "index_addr must produce an address of the same type as its base");
      require(IAI->getIndex()->getType().is<BuiltinIntegerType>(),
              "index_addr index must be of a builtin integer type");
   }

   void checkTailAddrInst(TailAddrInst *IAI) {
      require(IAI->getType().isAddress(), "tail_addr must produce an address");
      require(IAI->getIndex()->getType().is<BuiltinIntegerType>(),
              "tail_addr index must be of a builtin integer type");
   }

   void checkIndexRawPointerInst(IndexRawPointerInst *IAI) {
      require(IAI->getType().is<BuiltinRawPointerType>(),
              "index_raw_pointer must produce a RawPointer");
      require(IAI->getBase()->getType().is<BuiltinRawPointerType>(),
              "index_raw_pointer base must be a RawPointer");
      require(IAI->getIndex()->getType().is<BuiltinIntegerType>(),
              "index_raw_pointer index must be of a builtin integer type");
   }

   void checkTupleExtractInst(TupleExtractInst *EI) {
      CanTupleType operandTy = requireObjectType(TupleType, EI->getOperand(),
                                                 "Operand of tuple_extract");
      require(EI->getType().isObject(),
              "result of tuple_extract must be object");

      require(EI->getFieldNo() < operandTy->getNumElements(),
              "invalid field index for tuple_extract instruction");
      if (EI->getModule().getStage() != PILStage::Lowered) {
         require(EI->getType().getAstType() ==
                 operandTy.getElementType(EI->getFieldNo()),
                 "type of tuple_extract does not match type of element");
      }
   }

   void checkStructExtractInst(StructExtractInst *EI) {
      PILType operandTy = EI->getOperand()->getType();
      require(operandTy.isObject(),
              "cannot struct_extract from address");
      require(EI->getType().isObject(),
              "result of struct_extract cannot be address");
      StructDecl *sd = operandTy.getStructOrBoundGenericStruct();
      require(sd, "must struct_extract from struct");
      require(!sd->isResilient(F.getModule().getPolarphpModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient struct");
      require(!EI->getField()->isStatic(),
              "cannot get address of static property with struct_element_addr");
      require(EI->getField()->hasStorage(),
              "cannot load computed property with struct_extract");

      require(EI->getField()->getDeclContext() == sd,
              "struct_extract field is not a member of the struct");

      if (EI->getModule().getStage() != PILStage::Lowered) {
         PILType loweredFieldTy = operandTy.getFieldType(
            EI->getField(), F.getModule(), F.getTypeExpansionContext());
         require(loweredFieldTy == EI->getType(),
                 "result of struct_extract does not match type of field");
      }
   }

   void checkTupleElementAddrInst(TupleElementAddrInst *EI) {
      PILType operandTy = EI->getOperand()->getType();
      require(operandTy.isAddress(),
              "must derive element_addr from address");
      require(EI->getType().isAddress(),
              "result of tuple_element_addr must be address");
      require(operandTy.is<TupleType>(),
              "must derive tuple_element_addr from tuple");

      ArrayRef<TupleTypeElt> fields = operandTy.castTo<TupleType>()->getElements();
      require(EI->getFieldNo() < fields.size(),
              "invalid field index for element_addr instruction");
      if (EI->getModule().getStage() != PILStage::Lowered) {
         require(EI->getType().getAstType() ==
                 CanType(fields[EI->getFieldNo()].getType()),
                 "type of tuple_element_addr does not match type of element");
      }
   }

   void checkStructElementAddrInst(StructElementAddrInst *EI) {
      PILType operandTy = EI->getOperand()->getType();
      require(operandTy.isAddress(),
              "must derive struct_element_addr from address");
      StructDecl *sd = operandTy.getStructOrBoundGenericStruct();
      require(sd, "struct_element_addr operand must be struct address");
      require(!sd->isResilient(F.getModule().getPolarphpModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient struct");
      require(EI->getType().isAddress(),
              "result of struct_element_addr must be address");
      require(!EI->getField()->isStatic(),
              "cannot get address of static property with struct_element_addr");
      require(EI->getField()->hasStorage(),
              "cannot get address of computed property with struct_element_addr");

      require(EI->getField()->getDeclContext() == sd,
              "struct_element_addr field is not a member of the struct");

      if (EI->getModule().getStage() != PILStage::Lowered) {
         PILType loweredFieldTy = operandTy.getFieldType(
            EI->getField(), F.getModule(), F.getTypeExpansionContext());
         require(loweredFieldTy == EI->getType(),
                 "result of struct_element_addr does not match type of field");
      }
   }

   void checkRefElementAddrInst(RefElementAddrInst *EI) {
      requireReferenceValue(EI->getOperand(), "Operand of ref_element_addr");
      require(EI->getType().isAddress(),
              "result of ref_element_addr must be lvalue");
      require(!EI->getField()->isStatic(),
              "cannot get address of static property with struct_element_addr");
      require(EI->getField()->hasStorage(),
              "cannot get address of computed property with ref_element_addr");
      PILType operandTy = EI->getOperand()->getType();
      ClassDecl *cd = operandTy.getClassOrBoundGenericClass();
      require(cd, "ref_element_addr operand must be a class instance");
      require(!cd->isResilient(F.getModule().getPolarphpModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient class");

      require(EI->getField()->getDeclContext() == cd,
              "ref_element_addr field must be a member of the class");

      if (EI->getModule().getStage() != PILStage::Lowered) {
         PILType loweredFieldTy = operandTy.getFieldType(
            EI->getField(), F.getModule(), F.getTypeExpansionContext());
         require(loweredFieldTy == EI->getType(),
                 "result of ref_element_addr does not match type of field");
      }
      EI->getFieldNo();  // Make sure we can access the field without crashing.
   }

   void checkRefTailAddrInst(RefTailAddrInst *RTAI) {
      requireReferenceValue(RTAI->getOperand(), "Operand of ref_tail_addr");
      require(RTAI->getType().isAddress(),
              "result of ref_tail_addr must be lvalue");
      PILType operandTy = RTAI->getOperand()->getType();
      ClassDecl *cd = operandTy.getClassOrBoundGenericClass();
      require(cd, "ref_tail_addr operand must be a class instance");
      require(!cd->isResilient(F.getModule().getPolarphpModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient class");
      require(cd, "ref_tail_addr operand must be a class instance");
   }

   void checkDestructureStructInst(DestructureStructInst *DSI) {
      PILType operandTy = DSI->getOperand()->getType();
      StructDecl *sd = operandTy.getStructOrBoundGenericStruct();
      require(sd, "must struct_extract from struct");
      require(!sd->isResilient(F.getModule().getPolarphpModule(),
                               F.getResilienceExpansion()),
              "cannot access storage of resilient struct");
   }

   PILType getMethodSelfType(CanPILFunctionType ft) {
      return fnConv.getPILType(ft->getParameters().back());
   }

   void checkWitnessMethodInst(WitnessMethodInst *AMI) {
      auto methodType = requireObjectType(PILFunctionType, AMI,
                                          "result of witness_method");

      auto *protocol
         = dyn_cast<InterfaceDecl>(AMI->getMember().getDecl()->getDeclContext());
      require(protocol,
              "witness_method method must be a protocol method");

      require(methodType->getRepresentation()
              == F.getModule().Types.getInterfaceWitnessRepresentation(protocol),
              "result of witness_method must have correct representation for protocol");

      require(methodType->isPolymorphic(),
              "result of witness_method must be polymorphic");

      auto genericSig = methodType->getInvocationGenericSignature();

      auto selfGenericParam = genericSig->getGenericParams()[0];
      require(selfGenericParam->getDepth() == 0
              && selfGenericParam->getIndex() == 0,
              "method should be polymorphic on Self parameter at depth 0 index 0");
      Optional<Requirement> selfRequirement;
      for (auto req : genericSig->getRequirements()) {
         if (req.getKind() != RequirementKind::SameType) {
            selfRequirement = req;
            break;
         }
      }

      require(selfRequirement &&
                 selfRequirement->getKind() == RequirementKind::Conformance,
              "first non-same-typerequirement should be conformance requirement");
      auto conformsTo = genericSig->getConformsTo(selfGenericParam);
      require(std::find(conformsTo.begin(), conformsTo.end(), protocol)
              != conformsTo.end(),
              "requirement Self parameter must conform to called protocol");

      auto lookupType = AMI->getLookupType();
      if (getOpenedArchetypeOf(lookupType)) {
         require(AMI->getTypeDependentOperands().size() == 1,
                 "Must have a type dependent operand for the opened archetype");
         verifyOpenedArchetype(AMI, lookupType);
      } else {
         require(AMI->getTypeDependentOperands().empty(),
                 "Should not have an operand for the opened existential");
      }
      if (!isa<ArchetypeType>(lookupType)) {
         require(AMI->getConformance().isConcrete(),
                 "concrete type lookup requires concrete conformance");
         auto conformance = AMI->getConformance().getConcrete();
         require(conformance->getType()->isEqual(AMI->getLookupType()),
                 "concrete type lookup requires conformance that matches type");
      }

      require(AMI->getMember().requiresNewWitnessTableEntry(),
              "method does not have a witness table entry");
   }

   // Get the expected type of a dynamic method reference.
   PILType getDynamicMethodType(PILType selfType, PILDeclRef method) {
      auto &C = F.getAstContext();

      // The type of the dynamic method must match the usual type of the method,
      // but with the more opaque Self type.
      auto constantInfo =
         F.getModule().Types.getConstantInfo(F.getTypeExpansionContext(), method);
      auto methodTy = constantInfo.PILFnType;

      assert(!methodTy->isCoroutine());

      // Map interface types to archetypes.
      if (auto *env = F.getModule().Types.getConstantGenericEnvironment(method)) {
         auto subs = env->getForwardingSubstitutionMap();
         methodTy = methodTy->substGenericArgs(F.getModule(), subs,
                                               F.getTypeExpansionContext());
      }
      assert(!methodTy->isPolymorphic());

      // Replace Self parameter with type of 'self' at the call site.
      auto params = methodTy->getParameters();
      SmallVector<PILParameterInfo, 4>
         dynParams(params.begin(), params.end() - 1);
      dynParams.push_back(PILParameterInfo(selfType.getAstType(),
                                           params.back().getConvention()));

      auto results = methodTy->getResults();
      SmallVector<PILResultInfo, 4> dynResults(results.begin(), results.end());

      // If the method returns Self, substitute AnyObject for the result type.
      if (auto fnDecl = dyn_cast<FuncDecl>(method.getDecl())) {
         if (fnDecl->hasDynamicSelfResult()) {
            auto anyObjectTy = C.getAnyObjectType();
            for (auto &dynResult : dynResults) {
               auto newResultTy
                  = dynResult.getReturnValueType(F.getModule(), methodTy)
                     ->replaceCovariantResultType(anyObjectTy, 0);
               dynResult = PILResultInfo(newResultTy->getCanonicalType(),
                                         dynResult.getConvention());
            }
         }
      }

      auto fnTy = PILFunctionType::get(nullptr,
                                       methodTy->getExtInfo(),
                                       methodTy->getCoroutineKind(),
                                       methodTy->getCalleeConvention(),
                                       dynParams,
                                       methodTy->getYields(),
                                       dynResults,
                                       methodTy->getOptionalErrorResult(),
                                       SubstitutionMap(), false,
                                       F.getAstContext());
      return PILType::getPrimitiveObjectType(fnTy);
   }

   /// Visitor class that checks whether a given decl ref has an entry in the
   /// class's vtable.
   class VerifyClassMethodVisitor
      : public PILVTableVisitor<VerifyClassMethodVisitor>
   {
   public:
      PILDeclRef Method;
      bool Seen = false;

      VerifyClassMethodVisitor(PILDeclRef method)
         : Method(method.getOverriddenVTableEntry()) {
         auto *theClass = cast<ClassDecl>(Method.getDecl()->getDeclContext());
         addVTableEntries(theClass);
      }

      void addMethod(PILDeclRef method) {
         if (Seen)
            return;
         if (method == Method)
            Seen = true;
      }

      void addMethodOverride(PILDeclRef base, PILDeclRef derived) {}

      void addPlaceholder(MissingMemberDecl *) {}
   };

   void checkClassMethodInst(ClassMethodInst *CMI) {
      auto member = CMI->getMember();
      auto overrideTy =
         TC.getConstantOverrideType(F.getTypeExpansionContext(), member);
      if (CMI->getModule().getStage() != PILStage::Lowered) {
         requireSameType(
            CMI->getType(), PILType::getPrimitiveObjectType(overrideTy),
            "result type of class_method must match abstracted type of method");
      }
      auto methodType = requireObjectType(PILFunctionType, CMI,
                                          "result of class_method");
      require(!methodType->getExtInfo().hasContext(),
              "result method must be of a context-free function type");
      PILType operandType = CMI->getOperand()->getType();
      require(operandType.isClassOrClassMetatype(),
              "operand must be of a class type");
      require(getMethodSelfType(methodType).isClassOrClassMetatype(),
              "result must be a method of a class");

      require(!member.isForeign,
              "foreign method cannot be dispatched natively");
      require(!isa<ExtensionDecl>(member.getDecl()->getDeclContext()),
              "extension method cannot be dispatched natively");

      // The method ought to appear in the class vtable.
      require(VerifyClassMethodVisitor(member).Seen,
              "method does not appear in the class's vtable");
   }

   void checkSuperMethodInst(SuperMethodInst *CMI) {
      auto member = CMI->getMember();
      auto overrideTy =
         TC.getConstantOverrideType(F.getTypeExpansionContext(), member);
      if (CMI->getModule().getStage() != PILStage::Lowered) {
         requireSameType(
            CMI->getType(), PILType::getPrimitiveObjectType(overrideTy),
            "result type of super_method must match abstracted type of method");
      }
      auto methodType = requireObjectType(PILFunctionType, CMI,
                                          "result of super_method");
      require(!methodType->getExtInfo().hasContext(),
              "result method must be of a context-free function type");
      PILType operandType = CMI->getOperand()->getType();
      require(operandType.isClassOrClassMetatype(),
              "operand must be of a class type");
      require(getMethodSelfType(methodType).isClassOrClassMetatype(),
              "result must be a method of a class");

      require(!member.isForeign,
              "foreign method cannot be dispatched natively");
      require(!isa<ExtensionDecl>(member.getDecl()->getDeclContext()),
              "extension method cannot be dispatched natively");

      auto decl = CMI->getMember().getDecl();
      auto methodClass = decl->getDeclContext()->getDeclaredInterfaceType();

      require(methodClass->getClassOrBoundGenericClass(),
              "super_method must look up a class method");

      // The method ought to appear in the class vtable.
      require(VerifyClassMethodVisitor(member).Seen,
              "method does not appear in the class's vtable");
   }

   void checkObjCMethodInst(ObjCMethodInst *OMI) {
      auto member = OMI->getMember();
      require(member.isForeign,
              "native method cannot be dispatched via objc");

      auto methodType = requireObjectType(PILFunctionType, OMI,
                                          "result of objc_method");
      require(!methodType->getExtInfo().hasContext(),
              "result method must be of a context-free function type");
      require(methodType->getRepresentation()
              == PILFunctionTypeRepresentation::ObjCMethod,
              "wrong function type representation");

      auto operandType = OMI->getOperand()->getType();
      auto operandInstanceType = operandType.getAstType();
      if (auto metatypeType = dyn_cast<MetatypeType>(operandInstanceType))
         operandInstanceType = metatypeType.getInstanceType();

      if (operandInstanceType.getClassOrBoundGenericClass()) {
         auto overrideTy =
            TC.getConstantOverrideType(F.getTypeExpansionContext(), member);
         requireSameType(
            OMI->getType(), PILType::getPrimitiveObjectType(overrideTy),
            "result type of objc_method must match abstracted type of method");
      } else {
         require(isa<ArchetypeType>(operandInstanceType) ||
                 operandInstanceType->isObjCExistentialType(),
                 "operand type must be an archetype or self-conforming existential");
         verifyOpenedArchetype(OMI, OMI->getType().getAstType());
      }

      // TODO: We should enforce that ObjC methods are dispatched on ObjC
      // metatypes, but IRGen appears not to care right now.
#if 0
      if (auto metaTy = operandType.getAs<AnyMetatypeType>()) {
      bool objcMetatype
        = metaTy->getRepresentation() == MetatypeRepresentation::ObjC;
      require(objcMetatype,
              "objc class methods must be invoked on objc metatypes");
    }
#endif
   }

   void checkObjCSuperMethodInst(ObjCSuperMethodInst *OMI) {
      auto member = OMI->getMember();
      auto overrideTy =
         TC.getConstantOverrideType(F.getTypeExpansionContext(), member);
      if (OMI->getModule().getStage() != PILStage::Lowered) {
         requireSameType(
            OMI->getType(), PILType::getPrimitiveObjectType(overrideTy),
            "result type of super_method must match abstracted type of method");
      }
      auto methodType = requireObjectType(PILFunctionType, OMI,
                                          "result of objc_super_method");
      require(!methodType->getExtInfo().hasContext(),
              "result method must be of a context-free function type");
      PILType operandType = OMI->getOperand()->getType();
      require(operandType.isClassOrClassMetatype(),
              "operand must be of a class type");
      require(getMethodSelfType(methodType).isClassOrClassMetatype(),
              "result must be a method of a class");

      require(member.isForeign,
              "native method cannot be dispatched via objc");

      auto decl = member.getDecl();
      auto methodClass = decl->getDeclContext()->getDeclaredInterfaceType();

      require(methodClass->getClassOrBoundGenericClass(),
              "objc_super_method must look up a class method");
   }

   void checkOpenExistentialAddrInst(OpenExistentialAddrInst *OEI) {
      PILType operandType = OEI->getOperand()->getType();
      require(operandType.isAddress(),
              "open_existential_addr must be applied to address");
      require(operandType.canUseExistentialRepresentation(
         ExistentialRepresentation::Opaque),
              "open_existential_addr must be applied to opaque existential");

      require(OEI->getType().isAddress(),
              "open_existential_addr result must be an address");

      auto archetype = getOpenedArchetypeOf(OEI->getType().getAstType());
      require(archetype,
              "open_existential_addr result must be an opened existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential_addr should be registered in "
              "PILFunction");

      // Check all the uses. Consuming or mutating uses must have mutable access
      // to the opened value.
      auto allowedAccessKind = OEI->getAccessKind();
      if (allowedAccessKind == OpenedExistentialAccess::Mutable)
         return;

      require(allowedAccessKind == OpenedExistentialAccess::Mutable ||
              !ImmutableAddressUseVerifier().isMutatingOrConsuming(OEI),
              "open_existential_addr uses that consumes or mutates but is not "
              "opened for mutation");
   }

   void checkOpenExistentialRefInst(OpenExistentialRefInst *OEI) {
      PILType operandType = OEI->getOperand()->getType();
      require(operandType.isObject(),
              "open_existential_ref operand must not be address");

      require(operandType.canUseExistentialRepresentation(
         ExistentialRepresentation::Class),
              "open_existential_ref operand must be class existential");

      CanType resultInstanceTy = OEI->getType().getAstType();

      require(OEI->getType().isObject(),
              "open_existential_ref result must be an address");

      auto archetype = getOpenedArchetypeOf(resultInstanceTy);
      require(archetype,
              "open_existential_ref result must be an opened existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential_ref should be registered in "
              "PILFunction");
   }

   void checkOpenExistentialBoxInst(OpenExistentialBoxInst *OEI) {
      PILType operandType = OEI->getOperand()->getType();
      require(operandType.isObject(),
              "open_existential_box operand must not be address");

      require(operandType.canUseExistentialRepresentation(
         ExistentialRepresentation::Boxed),
              "open_existential_box operand must be boxed existential");

      CanType resultInstanceTy = OEI->getType().getAstType();

      require(OEI->getType().isAddress(),
              "open_existential_box result must be an address");

      auto archetype = getOpenedArchetypeOf(resultInstanceTy);
      require(archetype,
              "open_existential_box result must be an opened existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential_box should be registered in "
              "PILFunction");
   }

   void checkOpenExistentialBoxValueInst(OpenExistentialBoxValueInst *OEI) {
      PILType operandType = OEI->getOperand()->getType();
      require(operandType.isObject(),
              "open_existential_box operand must not be address");

      require(operandType.canUseExistentialRepresentation(
         ExistentialRepresentation::Boxed),
              "open_existential_box operand must be boxed existential");

      CanType resultInstanceTy = OEI->getType().getAstType();

      require(!OEI->getType().isAddress(),
              "open_existential_box_value result must not be an address");

      auto archetype = getOpenedArchetypeOf(resultInstanceTy);
      require(archetype,
              "open_existential_box_value result not an opened existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential_box_value should be "
              "registered in PILFunction");
   }

   void checkOpenExistentialMetatypeInst(OpenExistentialMetatypeInst *I) {
      PILType operandType = I->getOperand()->getType();
      require(operandType.isObject(),
              "open_existential_metatype operand must not be address");
      require(operandType.is<ExistentialMetatypeType>(),
              "open_existential_metatype operand must be existential metatype");
      require(operandType.castTo<ExistentialMetatypeType>()->hasRepresentation(),
              "open_existential_metatype operand must have a representation");

      PILType resultType = I->getType();
      require(resultType.isObject(),
              "open_existential_metatype result must not be address");
      require(resultType.is<MetatypeType>(),
              "open_existential_metatype result must be metatype");
      require(resultType.castTo<MetatypeType>()->hasRepresentation(),
              "open_existential_metatype result must have a representation");
      require(operandType.castTo<ExistentialMetatypeType>()->getRepresentation()
              == resultType.castTo<MetatypeType>()->getRepresentation(),
              "open_existential_metatype result must match representation of "
              "operand");

      CanType operandInstTy =
         operandType.castTo<ExistentialMetatypeType>().getInstanceType();
      CanType resultInstTy =
         resultType.castTo<MetatypeType>().getInstanceType();

      while (auto operandMetatype =
         dyn_cast<ExistentialMetatypeType>(operandInstTy)) {
         require(isa<MetatypeType>(resultInstTy),
                 "metatype depth mismatch in open_existential_metatype result");
         operandInstTy = operandMetatype.getInstanceType();
         resultInstTy = cast<MetatypeType>(resultInstTy).getInstanceType();
      }

      require(operandInstTy.isExistentialType(),
              "ill-formed existential metatype in open_existential_metatype "
              "operand");
      auto archetype = getOpenedArchetypeOf(resultInstTy);
      require(archetype, "open_existential_metatype result must be an opened "
                         "existential metatype");
      require(
         OpenedArchetypes.getOpenedArchetypeDef(archetype) == I,
         "Archetype opened by open_existential_metatype should be registered in "
         "PILFunction");
   }

   void checkOpenExistentialValueInst(OpenExistentialValueInst *OEI) {
      PILType operandType = OEI->getOperand()->getType();
      require(!operandType.isAddress(),
              "open_existential_value must not be applied to address");
      require(operandType.canUseExistentialRepresentation(
         ExistentialRepresentation::Opaque),
              "open_existential_value must be applied to opaque existential");

      require(!OEI->getType().isAddress(),
              "open_existential_value result must not be an address");

      auto archetype = getOpenedArchetypeOf(OEI->getType().getAstType());
      require(archetype, "open_existential_value result must be an opened "
                         "existential archetype");
      require(OpenedArchetypes.getOpenedArchetypeDef(archetype) == OEI,
              "Archetype opened by open_existential should be registered in "
              "PILFunction");
   }

   void checkAllocExistentialBoxInst(AllocExistentialBoxInst *AEBI) {
      PILType exType = AEBI->getExistentialType();
      require(exType.isObject(),
              "alloc_existential_box #0 result should be a value");
      require(exType.canUseExistentialRepresentation(
         ExistentialRepresentation::Boxed,
         AEBI->getFormalConcreteType()),
              "alloc_existential_box must be used with a boxed existential "
              "type");

      checkExistentialInterfaceConformances(exType.getAstType(),
                                            AEBI->getFormalConcreteType(),
                                            AEBI->getConformances());
      verifyOpenedArchetype(AEBI, AEBI->getFormalConcreteType());
   }

   void checkInitExistentialAddrInst(InitExistentialAddrInst *AEI) {
      PILType exType = AEI->getOperand()->getType();
      require(exType.isAddress(),
              "init_existential_addr must be applied to an address");
      require(exType.canUseExistentialRepresentation(
         ExistentialRepresentation::Opaque,
         AEI->getFormalConcreteType()),
              "init_existential_addr must be used with an opaque "
              "existential type");

      // The lowered type must be the properly-abstracted form of the AST type.
      auto archetype = OpenedArchetypeType::get(exType.getAstType());

      auto loweredTy = F.getLoweredType(lowering::AbstractionPattern(archetype),
                                        AEI->getFormalConcreteType())
         .getAddressType();

      requireSameType(loweredTy, AEI->getLoweredConcreteType(),
                      "init_existential_addr result type must be the lowered "
                      "concrete type at the right abstraction level");

      require(isLoweringOf(AEI->getLoweredConcreteType(),
                           AEI->getFormalConcreteType()),
              "init_existential_addr payload must be a lowering of the formal "
              "concrete type");

      checkExistentialInterfaceConformances(exType.getAstType(),
                                            AEI->getFormalConcreteType(),
                                            AEI->getConformances());
      verifyOpenedArchetype(AEI, AEI->getFormalConcreteType());
   }

   void checkInitExistentialValueInst(InitExistentialValueInst *IEI) {
      PILType concreteType = IEI->getOperand()->getType();
      require(!concreteType.isAddress(),
              "init_existential_value must not be used on addresses");
      require(!IEI->getType().isAddress(),
              "init_existential_value result must not be an address");
      // The operand must be at the right abstraction level for the existential.
      PILType exType = IEI->getType();
      auto archetype = OpenedArchetypeType::get(exType.getAstType());
      auto loweredTy = F.getLoweredType(lowering::AbstractionPattern(archetype),
                                        IEI->getFormalConcreteType());
      requireSameType(
         concreteType, loweredTy,
         "init_existential_value operand must be lowered to the right "
         "abstraction level for the existential");

      require(isLoweringOf(IEI->getOperand()->getType(),
                           IEI->getFormalConcreteType()),
              "init_existential_value operand must be a lowering of the formal "
              "concrete type");

      checkExistentialInterfaceConformances(exType.getAstType(),
                                            IEI->getFormalConcreteType(),
                                            IEI->getConformances());
      verifyOpenedArchetype(IEI, IEI->getFormalConcreteType());
   }

   void checkInitExistentialRefInst(InitExistentialRefInst *IEI) {
      PILType concreteType = IEI->getOperand()->getType();
      require(concreteType.getAstType()->isBridgeableObjectType(),
              "init_existential_ref operand must be a class instance");
      require(IEI->getType().canUseExistentialRepresentation(
         ExistentialRepresentation::Class,
         IEI->getFormalConcreteType()),
              "init_existential_ref must be used with a class existential type");
      require(IEI->getType().isObject(),
              "init_existential_ref result must not be an address");

      // The operand must be at the right abstraction level for the existential.
      PILType exType = IEI->getType();
      auto archetype = OpenedArchetypeType::get(exType.getAstType());
      auto loweredTy = F.getLoweredType(lowering::AbstractionPattern(archetype),
                                        IEI->getFormalConcreteType());
      requireSameType(concreteType, loweredTy,
                      "init_existential_ref operand must be lowered to the right "
                      "abstraction level for the existential");

      require(isLoweringOf(IEI->getOperand()->getType(),
                           IEI->getFormalConcreteType()),
              "init_existential_ref operand must be a lowering of the formal "
              "concrete type");

      checkExistentialInterfaceConformances(exType.getAstType(),
                                            IEI->getFormalConcreteType(),
                                            IEI->getConformances());
      verifyOpenedArchetype(IEI, IEI->getFormalConcreteType());
   }

   void checkDeinitExistentialAddrInst(DeinitExistentialAddrInst *DEI) {
      PILType exType = DEI->getOperand()->getType();
      require(exType.isAddress(),
              "deinit_existential_addr must be applied to an address");
      require(exType.canUseExistentialRepresentation(
         ExistentialRepresentation::Opaque),
              "deinit_existential_addr must be applied to an opaque existential");
   }

   void checkDeinitExistentialValueInst(DeinitExistentialValueInst *DEI) {
      PILType exType = DEI->getOperand()->getType();
      require(!exType.isAddress(),
              "deinit_existential_value must not be applied to an address");
      require(
         exType.canUseExistentialRepresentation(
            ExistentialRepresentation::Opaque),
         "deinit_existential_value must be applied to an opaque existential");
   }

   void checkDeallocExistentialBoxInst(DeallocExistentialBoxInst *DEBI) {
      PILType exType = DEBI->getOperand()->getType();
      require(exType.isObject(),
              "dealloc_existential_box must be applied to a value");
      require(exType.canUseExistentialRepresentation(
         ExistentialRepresentation::Boxed),
              "dealloc_existential_box must be applied to a boxed "
              "existential");
   }

   void checkInitExistentialMetatypeInst(InitExistentialMetatypeInst *I) {
      PILType operandType = I->getOperand()->getType();
      require(operandType.isObject(),
              "init_existential_metatype operand must not be an address");
      require(operandType.is<MetatypeType>(),
              "init_existential_metatype operand must be a metatype");
      require(operandType.castTo<MetatypeType>()->hasRepresentation(),
              "init_existential_metatype operand must have a representation");

      PILType resultType = I->getType();
      require(resultType.is<ExistentialMetatypeType>(),
              "init_existential_metatype result must be an existential metatype");
      auto MetaTy = resultType.castTo<ExistentialMetatypeType>();
      require(resultType.isObject(),
              "init_existential_metatype result must not be an address");
      require(MetaTy->hasRepresentation(),
              "init_existential_metatype result must have a representation");
      require(MetaTy->getRepresentation()
              == operandType.castTo<MetatypeType>()->getRepresentation(),
              "init_existential_metatype result must match representation of "
              "operand");

      auto resultInstanceType = resultType.getAstType();
      auto operandInstanceType = operandType.getAstType();
      while (isa<ExistentialMetatypeType>(resultInstanceType)) {
         resultInstanceType =
            cast<ExistentialMetatypeType>(resultInstanceType).getInstanceType();
         operandInstanceType =
            cast<MetatypeType>(operandInstanceType).getInstanceType();
      }

      checkExistentialInterfaceConformances(resultInstanceType,
                                            operandInstanceType,
                                            I->getConformances());
      verifyOpenedArchetype(I, MetaTy.getInstanceType());
   }

   void checkExistentialInterfaceConformances(CanType resultType,
                                              CanType concreteType,
                                              ArrayRef<InterfaceConformanceRef> conformances) {
      auto layout = resultType.getExistentialLayout();
      auto protocols = layout.getInterfaces();

      require(conformances.size() == protocols.size(),
              "init_existential instruction must have the "
              "right number of conformances");

      if (layout.requiresClass()) {
         require(concreteType->mayHaveSuperclass() ||
                 (concreteType.isExistentialType() &&
                  concreteType.getExistentialLayout().requiresClass()),
                 "init_existential of class existential with non-class type");
      }

      if (auto superclass = layout.getSuperclass()) {
         require(superclass->isExactSuperclassOf(concreteType),
                 "init_existential of subclass existential with wrong type");
      }

      for (auto i : indices(conformances)) {
         require(conformances[i].getRequirement() == protocols[i]->getDecl(),
                 "init_existential instruction must have conformances in "
                 "proper order");
      }
   }

   void verifyCheckedCast(bool isExact, PILType fromTy, PILType toTy,
                          bool isOpaque = false) {
      // Verify common invariants.
      require(fromTy.isObject() && toTy.isObject(),
              "value checked cast src and dest must be objects");

      auto fromCanTy = fromTy.getAstType();
      auto toCanTy = toTy.getAstType();

      require(isOpaque || canUseScalarCheckedCastInstructions(F.getModule(),
                                                              fromCanTy, toCanTy),
              "invalid value checked cast src or dest types");

      // Peel off metatypes. If two types are checked-cast-able, so are their
      // metatypes.
      unsigned MetatyLevel = 0;
      while (isa<AnyMetatypeType>(fromCanTy) && isa<AnyMetatypeType>(toCanTy)) {
         auto fromMetaty = cast<AnyMetatypeType>(fromCanTy);
         auto toMetaty = cast<AnyMetatypeType>(toCanTy);

         // Check representations only for the top-level metatypes as only
         // those are PIL-lowered.
         if (!MetatyLevel) {
            // The representations must match.
            require(fromMetaty->getRepresentation() == toMetaty->getRepresentation(),
                    "metatype checked cast cannot change metatype representation");

            // We can't handle the 'thin' case yet, but it shouldn't really even be
            // interesting.
            require(fromMetaty->getRepresentation() != MetatypeRepresentation::Thin,
                    "metatype checked cast cannot check thin metatypes");
         }

         fromCanTy = fromMetaty.getInstanceType();
         toCanTy = toMetaty.getInstanceType();
         MetatyLevel++;
      }

      if (isExact) {
         require(fromCanTy.getClassOrBoundGenericClass(),
                 "downcast operand must be a class type");
         require(toCanTy.getClassOrBoundGenericClass(),
                 "downcast must convert to a class type");
         require(fromCanTy->isBindableToSuperclassOf(toCanTy),
                 "downcast must convert to a subclass");
      }
   }

   void checkUnconditionalCheckedCastInst(UnconditionalCheckedCastInst *CI) {
      verifyCheckedCast(/*exact*/ false,
                                  CI->getOperand()->getType(),
                                  CI->getType());
      verifyOpenedArchetype(CI, CI->getType().getAstType());
   }

   void checkUnconditionalCheckedCastValueInst(
      UnconditionalCheckedCastValueInst *CI) {
      verifyCheckedCast(/*exact*/ false, CI->getOperand()->getType(),
                                  CI->getType(), true);
      verifyOpenedArchetype(CI, CI->getType().getAstType());
   }

   /// Verify if a given type is or contains an opened archetype or dynamic self.
   /// If this is the case, verify that the provided instruction has a type
   /// dependent operand for it.
   void verifyOpenedArchetype(PILInstruction *I, CanType Ty) {
      if (!Ty)
         return;
      // Check the type and all of its contained types.
      Ty.visit([&](CanType t) {
         PILValue Def;
         if (t->isOpenedExistential()) {
            auto archetypeTy = cast<ArchetypeType>(t);
            Def = OpenedArchetypes.getOpenedArchetypeDef(archetypeTy);
            require(Def, "Opened archetype should be registered in PILFunction");
         } else if (t->hasDynamicSelfType()) {
            require(I->getFunction()->hasSelfParam() ||
                    I->getFunction()->hasSelfMetadataParam(),
                    "Function containing dynamic self type must have self parameter");
            if (I->getFunction()->hasSelfMetadataParam())
               Def = I->getFunction()->getArguments().back();
            else
               Def = I->getFunction()->getSelfArgument();
         } else {
            return;
         }
         for (auto &TypeDefOp : I->getTypeDependentOperands()) {
            if (TypeDefOp.get() == Def)
               return;
         }
         require(false, "Instruction should contain a type dependent operand for "
                        "every used open archetype or dynamic self");
      });
   }

   void checkCheckedCastBranchInst(CheckedCastBranchInst *CBI) {
      verifyCheckedCast(CBI->isExact(),
                        CBI->getSourceLoweredType(),
                        CBI->getTargetLoweredType());
      verifyOpenedArchetype(CBI, CBI->getTargetFormalType());

      require(CBI->getSuccessBB()->args_size() == 1,
              "success dest of checked_cast_br must take one argument");
      require(CBI->getSuccessBB()->args_begin()[0]->getType() ==
              CBI->getTargetLoweredType(),
              "success dest block argument of checked_cast_br must match type of "
              "cast");
      require(!F.hasOwnership() || CBI->getFailureBB()->args_size() == 1,
              "failure dest of checked_cast_br must take one argument in "
              "ownership qualified sil");
      require(!F.hasOwnership() ||
              CBI->getFailureBB()->args_begin()[0]->getType() ==
              CBI->getOperand()->getType(),
              "failure dest block argument must match type of original type in "
              "ownership qualified sil");
      require(F.hasOwnership() || CBI->getFailureBB()->args_empty(),
              "Failure dest of checked_cast_br must not take any argument in "
              "non-ownership qualified sil");
   }

   void checkCheckedCastValueBranchInst(CheckedCastValueBranchInst *CBI) {
      verifyCheckedCast(false,
                        CBI->getSourceLoweredType(),
                        CBI->getTargetLoweredType(),
                        true);
      verifyOpenedArchetype(CBI, CBI->getTargetFormalType());

      require(CBI->getSuccessBB()->args_size() == 1,
              "success dest of checked_cast_value_br must take one argument");
      require(CBI->getSuccessBB()->args_begin()[0]->getType() ==
              CBI->getTargetLoweredType(),
              "success dest block argument of checked_cast_value_br must match "
              "type of cast");
      require(F.hasOwnership() || CBI->getFailureBB()->args_empty(),
              "failure dest of checked_cast_value_br in unqualified ownership "
              "sil must take no arguments");
   }

   void checkCheckedCastAddrBranchInst(CheckedCastAddrBranchInst *CCABI) {
      require(CCABI->getSrc()->getType().isAddress(),
              "checked_cast_addr_br src must be an address");
      require(CCABI->getDest()->getType().isAddress(),
              "checked_cast_addr_br dest must be an address");

      require(
         CCABI->getSuccessBB()->args_size() == 0,
         "success dest block of checked_cast_addr_br must not take an argument");
      require(
         CCABI->getFailureBB()->args_size() == 0,
         "failure dest block of checked_cast_addr_br must not take an argument");
   }

   void checkThinToThickFunctionInst(ThinToThickFunctionInst *TTFI) {
      auto opFTy = requireObjectType(PILFunctionType, TTFI->getOperand(),
                                     "thin_to_thick_function operand");
      auto resFTy = requireObjectType(PILFunctionType, TTFI,
                                      "thin_to_thick_function result");
      require(opFTy->isPolymorphic() == resFTy->isPolymorphic(),
              "thin_to_thick_function operand and result type must differ only "
              " in thinness");
      requireSameFunctionComponents(opFTy, resFTy,
                                    "thin_to_thick_function operand and result");

      require(opFTy->getRepresentation() == PILFunctionType::Representation::Thin,
              "operand of thin_to_thick_function must be thin");
      require(resFTy->getRepresentation() == PILFunctionType::Representation::Thick,
              "result of thin_to_thick_function must be thick");

      auto adjustedOperandExtInfo =
         opFTy->getExtInfo()
            .withRepresentation(PILFunctionType::Representation::Thick)
            .withNoEscape(resFTy->isNoEscape());
      require(adjustedOperandExtInfo == resFTy->getExtInfo(),
              "operand and result of thin_to_think_function must agree in particulars");
   }

   // @todo
//   void checkThickToObjCMetatypeInst(ThickToObjCMetatypeInst *TTOCI) {
//      auto opTy = requireObjectType(AnyMetatypeType, TTOCI->getOperand(),
//                                    "thick_to_objc_metatype operand");
//      auto resTy = requireObjectType(AnyMetatypeType, TTOCI,
//                                     "thick_to_objc_metatype result");
//
//      require(TTOCI->getOperand()->getType().is<MetatypeType>() ==
//              TTOCI->getType().is<MetatypeType>(),
//              "thick_to_objc_metatype cannot change metatype kinds");
//      require(opTy->getRepresentation() == MetatypeRepresentation::Thick,
//              "operand of thick_to_objc_metatype must be thick");
//      require(resTy->getRepresentation() == MetatypeRepresentation::ObjC,
//              "operand of thick_to_objc_metatype must be ObjC");
//
//      require(opTy->getInstanceType()->isEqual(resTy->getInstanceType()),
//              "thick_to_objc_metatype instance types do not match");
//   }
//
//   void checkObjCToThickMetatypeInst(ObjCToThickMetatypeInst *OCTTI) {
//      auto opTy = requireObjectType(AnyMetatypeType, OCTTI->getOperand(),
//                                    "objc_to_thick_metatype operand");
//      auto resTy = requireObjectType(AnyMetatypeType, OCTTI,
//                                     "objc_to_thick_metatype result");
//
//      require(OCTTI->getOperand()->getType().is<MetatypeType>() ==
//              OCTTI->getType().is<MetatypeType>(),
//              "objc_to_thick_metatype cannot change metatype kinds");
//      require(opTy->getRepresentation() == MetatypeRepresentation::ObjC,
//              "operand of objc_to_thick_metatype must be ObjC");
//      require(resTy->getRepresentation() == MetatypeRepresentation::Thick,
//              "operand of objc_to_thick_metatype must be thick");
//
//      require(opTy->getInstanceType()->isEqual(resTy->getInstanceType()),
//              "objc_to_thick_metatype instance types do not match");
//   }

   void checkUpcastInst(UpcastInst *UI) {
      require(UI->getType() != UI->getOperand()->getType(),
              "can't upcast to same type");
      if (UI->getType().is<MetatypeType>()) {
         CanType instTy(UI->getType().castTo<MetatypeType>()->getInstanceType());
         require(UI->getOperand()->getType().is<MetatypeType>(),
                 "upcast operand must be a class or class metatype instance");
         CanType opInstTy(UI->getOperand()->getType().castTo<MetatypeType>()
                             ->getInstanceType());
         auto instClass = instTy->getClassOrBoundGenericClass();
         require(instClass,
                 "upcast must convert a class metatype to a class metatype");

//         if (instClass->usesObjCGenericsModel()) {
//            require(instClass->getDeclaredTypeInContext()
//                       ->isBindableToSuperclassOf(opInstTy),
//                    "upcast must cast to a superclass or an existential metatype");
//         } else {
         // @todo
         require(instTy->isExactSuperclassOf(opInstTy),
                 "upcast must cast to a superclass or an existential metatype");
//         }
         return;
      }

      require(UI->getType().getCategory() ==
              UI->getOperand()->getType().getCategory(),
              "Upcast can only upcast in between types of the same "
              "PILValueCategory. This prevents address types from being cast to "
              "object types or vis-a-versa");

      auto ToTy = UI->getType();
      auto FromTy = UI->getOperand()->getType();

      // Upcast from Optional<B> to Optional<A> is legal as long as B is a
      // subclass of A.
      if (ToTy.getAstType().getOptionalObjectType() &&
          FromTy.getAstType().getOptionalObjectType()) {
         ToTy = PILType::getPrimitiveObjectType(
            ToTy.getAstType().getOptionalObjectType());
         FromTy = PILType::getPrimitiveObjectType(
            FromTy.getAstType().getOptionalObjectType());
      }

      auto ToClass = ToTy.getClassOrBoundGenericClass();
      require(ToClass,
              "upcast must convert a class instance to a class type");
//      if (ToClass->usesObjCGenericsModel()) {
//         require(ToClass->getDeclaredTypeInContext()
//                    ->isBindableToSuperclassOf(FromTy.getAstType()),
//                 "upcast must cast to a superclass or an existential metatype");
//      } else {
      // @todo
      require(ToTy.isExactSuperclassOf(FromTy),
              "upcast must cast to a superclass or an existential metatype");
//      }
   }

   void checkAddressToPointerInst(AddressToPointerInst *AI) {
      require(AI->getOperand()->getType().isAddress(),
              "address-to-pointer operand must be an address");
      require(AI->getType().getAstType()->isEqual(
         AI->getType().getAstContext().TheRawPointerType),
              "address-to-pointer result type must be RawPointer");
   }

   void checkUncheckedRefCastInst(UncheckedRefCastInst *AI) {
      verifyOpenedArchetype(AI, AI->getType().getAstType());
      require(AI->getOperand()->getType().isObject(),
              "unchecked_ref_cast operand must be a value");
      require(AI->getType().isObject(),
              "unchecked_ref_cast result must be an object");
      require(PILType::canRefCast(AI->getOperand()->getType(), AI->getType(),
                                  AI->getModule()),
              "unchecked_ref_cast requires a heap object reference type");
   }

   void checkUncheckedRefCastAddrInst(UncheckedRefCastAddrInst *AI) {
      auto srcTy = AI->getSrc()->getType();
      auto destTy = AI->getDest()->getType();
      require(srcTy.isAddress(),
              "unchecked_ref_cast_addr operand must be an address");
      require(destTy.isAddress(),
              "unchecked_ref_cast_addr result must be an address");
      // The static src/dest types cannot be checked here even if they are
      // loadable. unchecked_ref_cast_addr may accept nonreference static types
      // (as a result of specialization). These cases will never be promoted to
      // value bitcast, thus will cause the subsequent runtime cast to fail.
   }

   void checkUncheckedAddrCastInst(UncheckedAddrCastInst *AI) {
      verifyOpenedArchetype(AI, AI->getType().getAstType());

      require(AI->getOperand()->getType().isAddress(),
              "unchecked_addr_cast operand must be an address");
      require(AI->getType().isAddress(),
              "unchecked_addr_cast result must be an address");
   }

   void checkUncheckedTrivialBitCastInst(UncheckedTrivialBitCastInst *BI) {
      verifyOpenedArchetype(BI, BI->getType().getAstType());
      require(BI->getOperand()->getType().isObject(),
              "unchecked_trivial_bit_cast must operate on a value");
      require(BI->getType().isObject(),
              "unchecked_trivial_bit_cast must produce a value");
      require(BI->getType().isTrivial(F),
              "unchecked_trivial_bit_cast must produce a value of trivial type");
   }

   void checkUncheckedBitwiseCastInst(UncheckedBitwiseCastInst *BI) {
      verifyOpenedArchetype(BI, BI->getType().getAstType());
      require(BI->getOperand()->getType().isObject(),
              "unchecked_bitwise_cast must operate on a value");
      require(BI->getType().isObject(),
              "unchecked_bitwise_cast must produce a value");
   }

   void checkRefToRawPointerInst(RefToRawPointerInst *AI) {
      require(AI->getOperand()->getType().isAnyClassReferenceType(),
              "ref-to-raw-pointer operand must be a class reference or"
              " NativeObject");
      require(AI->getType().getAstType()->isEqual(
         AI->getType().getAstContext().TheRawPointerType),
              "ref-to-raw-pointer result must be RawPointer");
   }

   void checkRawPointerToRefInst(RawPointerToRefInst *AI) {
      verifyOpenedArchetype(AI, AI->getType().getAstType());
      require(AI->getType()
                 .getAstType()->isBridgeableObjectType()
              || AI->getType().getAstType()->isEqual(
         AI->getType().getAstContext().TheNativeObjectType),
              "raw-pointer-to-ref result must be a class reference or NativeObject");
      require(AI->getOperand()->getType().getAstType()->isEqual(
         AI->getType().getAstContext().TheRawPointerType),
              "raw-pointer-to-ref operand must be NativeObject");
   }

   void checkRefToBridgeObjectInst(RefToBridgeObjectInst *RI) {
      require(RI->getConverted()->getType().isObject(),
              "ref_to_bridge_object must convert from a value");
      require(RI->getConverted()->getType().getAstType()
                 ->isBridgeableObjectType(),
              "ref_to_bridge_object must convert from a heap object ref");
      require(RI->getBitsOperand()->getType()
              == PILType::getBuiltinWordType(F.getAstContext()),
              "ref_to_bridge_object must take a Builtin.Word bits operand");
      require(RI->getType() == PILType::getBridgeObjectType(F.getAstContext()),
              "ref_to_bridge_object must produce a BridgeObject");
   }

   void checkBridgeObjectToRefInst(BridgeObjectToRefInst *RI) {
      verifyOpenedArchetype(RI, RI->getType().getAstType());
      require(RI->getConverted()->getType()
              == PILType::getBridgeObjectType(F.getAstContext()),
              "bridge_object_to_ref must take a BridgeObject");
      require(RI->getType().isObject(),
              "bridge_object_to_ref must produce a value");
      require(RI->getType().getAstType()->isBridgeableObjectType(),
              "bridge_object_to_ref must produce a heap object reference");
   }
   void checkBridgeObjectToWordInst(BridgeObjectToWordInst *RI) {
      require(RI->getConverted()->getType()
              == PILType::getBridgeObjectType(F.getAstContext()),
              "bridge_object_to_word must take a BridgeObject");
      require(RI->getType().isObject(),
              "bridge_object_to_word must produce a value");
      require(RI->getType() == PILType::getBuiltinWordType(F.getAstContext()),
              "bridge_object_to_word must produce a Word");
   }

   void checkConvertFunctionInst(ConvertFunctionInst *ICI) {
      auto opTI = requireObjectType(PILFunctionType, ICI->getOperand(),
                                    "convert_function operand");
      auto resTI = requireObjectType(PILFunctionType, ICI,
                                     "convert_function result");

      // convert_function is required to be an ABI-compatible conversion.
      requireABICompatibleFunctionTypes(
         opTI, resTI, "convert_function cannot change function ABI",
         *ICI->getFunction());
   }

   void checkConvertEscapeToNoEscapeInst(ConvertEscapeToNoEscapeInst *ICI) {
      auto opTI = requireObjectType(PILFunctionType, ICI->getOperand(),
                                    "convert_escape_to_noescape operand");
      auto resTI = ICI->getType().castTo<PILFunctionType>();

      // FIXME: Not yet, to be enabled when this is true.
      // require(resTI->isTrivial(F.getModule()),
      //         "convert_escape_to_noescape should produce a trivial result type");

      // convert_escape_to_noescape is required to be an ABI-compatible
      // conversion once escapability is the same on both sides.
      requireABICompatibleFunctionTypes(
         opTI, resTI->getWithExtInfo(resTI->getExtInfo().withNoEscape(false)),
         "convert_escape_to_noescape cannot change function ABI",
         *ICI->getFunction());

      // After mandatory passes convert_escape_to_noescape should not have the
      // '[not_guaranteed]' or '[escaped]' attributes.
      if (!SkipConvertEscapeToNoescapeAttributes &&
          F.getModule().getStage() != PILStage::Raw) {
         require(ICI->isLifetimeGuaranteed(),
                 "convert_escape_to_noescape [not_guaranteed] not "
                 "allowed after mandatory passes");
      }
   }

   void checkThinFunctionToPointerInst(ThinFunctionToPointerInst *CI) {
      auto opTI = requireObjectType(PILFunctionType, CI->getOperand(),
                                    "thin_function_to_pointer operand");
      requireObjectType(BuiltinRawPointerType, CI,
                        "thin_function_to_pointer result");

      auto rep = opTI->getRepresentation();
      require(rep == PILFunctionTypeRepresentation::Thin ||
              rep == PILFunctionTypeRepresentation::Method ||
              rep == PILFunctionTypeRepresentation::WitnessMethod,
              "thin_function_to_pointer only works on thin, method or "
              "witness_method functions");
   }

   void checkPointerToThinFunctionInst(PointerToThinFunctionInst *CI) {
      auto resultTI = requireObjectType(PILFunctionType, CI,
                                        "pointer_to_thin_function result");
      requireObjectType(BuiltinRawPointerType, CI->getOperand(),
                        "pointer_to_thin_function operand");

      auto rep = resultTI->getRepresentation();
      require(rep == PILFunctionTypeRepresentation::Thin ||
              rep == PILFunctionTypeRepresentation::Method ||
              rep == PILFunctionTypeRepresentation::WitnessMethod,
              "pointer_to_thin_function only works on thin, method or "
              "witness_method functions");
   }

   void checkCondFailInst(CondFailInst *CFI) {
      require(CFI->getOperand()->getType()
              == PILType::getBuiltinIntegerType(1, F.getAstContext()),
              "cond_fail operand must be a Builtin.Int1");
   }

   void checkReturnInst(ReturnInst *RI) {
      LLVM_DEBUG(RI->print(llvm::dbgs()));

      PILType functionResultType =
         F.getLoweredType(
               F.mapTypeIntoContext(fnConv.getPILResultType()).getAstType())
            .getCategoryType(fnConv.getPILResultType().getCategory());
      PILType instResultType = RI->getOperand()->getType();
      LLVM_DEBUG(llvm::dbgs() << "function return type: ";
                    functionResultType.dump();
                    llvm::dbgs() << "return inst type: ";
                    instResultType.dump(););
      require(functionResultType == instResultType,
              "return value type does not match return type of function");
   }

   void checkThrowInst(ThrowInst *TI) {
      LLVM_DEBUG(TI->print(llvm::dbgs()));

      CanPILFunctionType fnType =
         F.getLoweredFunctionTypeInContext(F.getTypeExpansionContext());
      require(fnType->hasErrorResult(),
              "throw in function that doesn't have an error result");

      PILType functionResultType =
         F.getLoweredType(
               F.mapTypeIntoContext(fnConv.getPILErrorType()).getAstType())
            .getCategoryType(fnConv.getPILErrorType().getCategory());
      PILType instResultType = TI->getOperand()->getType();
      LLVM_DEBUG(llvm::dbgs() << "function error result type: ";
                    functionResultType.dump();
                    llvm::dbgs() << "throw operand type: ";
                    instResultType.dump(););
      require(functionResultType == instResultType,
              "throw operand type does not match error result type of function");
   }

   void checkUnwindInst(UnwindInst *UI) {
      require(F.getLoweredFunctionType()->isCoroutine(),
              "unwind in non-coroutine function");
   }

   void checkYieldInst(YieldInst *YI) {
      CanPILFunctionType fnType =
         F.getLoweredFunctionTypeInContext(F.getTypeExpansionContext());
      require(fnType->isCoroutine(),
              "yield in non-coroutine function");

      auto yieldedValues = YI->getYieldedValues();
      auto yieldInfos = fnType->getYields();
      require(yieldedValues.size() == yieldInfos.size(),
              "wrong number of yielded values for function");
      for (auto i : indices(yieldedValues)) {
         PILType yieldType =
            F.mapTypeIntoContext(fnConv.getPILType(yieldInfos[i]));
         require(yieldedValues[i]->getType() == yieldType,
                 "yielded value does not match yield type of coroutine");
      }

      // We require the resume and unwind destinations to be unique in order
      // to prevent either edge from becoming critical.
      require(YI->getResumeBB()->getSinglePredecessorBlock(),
              "resume dest of 'yield' must be uniquely used");
      require(YI->getUnwindBB()->getSinglePredecessorBlock(),
              "unwind dest of 'yield' must be uniquely used");
   }

   void checkSelectEnumCases(SelectEnumInstBase *I) {
      EnumDecl *eDecl = I->getEnumOperand()->getType().getEnumOrBoundGenericEnum();
      require(eDecl, "select_enum operand must be an enum");

      // Find the set of enum elements for the type so we can verify
      // exhaustiveness.
      llvm::DenseSet<EnumElementDecl*> unswitchedElts;
      eDecl->getAllElements(unswitchedElts);

      // Verify the set of enum cases we dispatch on.
      for (unsigned i = 0, e = I->getNumCases(); i < e; ++i) {
         EnumElementDecl *elt;
         PILValue result;
         std::tie(elt, result) = I->getCase(i);

         require(elt->getDeclContext() == eDecl,
                 "select_enum dispatches on enum element that is not part of "
                 "its type");
         require(unswitchedElts.count(elt),
                 "select_enum dispatches on same enum element more than once");
         unswitchedElts.erase(elt);

         // The result value must match the type of the instruction.
         requireSameType(result->getType(), I->getType(),
                         "select_enum case operand must match type of instruction");
      }

      // If the select is non-exhaustive, we require a default.
      bool isExhaustive =
         eDecl->isEffectivelyExhaustive(F.getModule().getPolarphpModule(),
                                        F.getResilienceExpansion());
      require((isExhaustive && unswitchedElts.empty()) || I->hasDefault(),
              "nonexhaustive select_enum must have a default destination");
      if (I->hasDefault()) {
         requireSameType(I->getDefaultResult()->getType(),
                         I->getType(),
                         "select_enum default operand must match type of instruction");
      }
   }

   void checkSelectEnumInst(SelectEnumInst *SEI) {
      require(SEI->getEnumOperand()->getType().isObject(),
              "select_enum operand must be an object");

      checkSelectEnumCases(SEI);
   }
   void checkSelectEnumAddrInst(SelectEnumAddrInst *SEI) {
      require(SEI->getEnumOperand()->getType().isAddress(),
              "select_enum_addr operand must be an address");

      checkSelectEnumCases(SEI);
   }

   void checkSwitchValueInst(SwitchValueInst *SVI) {
      // TODO: Type should be either integer or function
      auto Ty = SVI->getOperand()->getType();
      require(Ty.is<BuiltinIntegerType>() || Ty.is<PILFunctionType>(),
              "switch_value operand should be either of an integer "
              "or function type");

      auto ult = [](const PILValue &a, const PILValue &b) {
         return a == b || a < b;
      };

      std::set<PILValue, decltype(ult)> cases(ult);

      for (unsigned i = 0, e = SVI->getNumCases(); i < e; ++i) {
         PILValue value;
         PILBasicBlock *dest;
         std::tie(value, dest) = SVI->getCase(i);

         require(value->getType() == Ty,
                 "switch_value case value should have the same type as its operand");

         require(!cases.count(value),
                 "multiple switch_value cases for same value");
         cases.insert(value);

         require(dest->args_empty(),
                 "switch_value case destination cannot take arguments");
      }

      if (SVI->hasDefault())
         require(SVI->getDefaultBB()->args_empty(),
                 "switch_value default destination cannot take arguments");
   }

   void checkSelectValueCases(SelectValueInst *I) {
      struct APIntCmp {
         bool operator()(const APInt &a, const APInt &b) const {
            return a.ult(b);
         };
      };

      llvm::SmallSet<APInt, 16, APIntCmp> seenCaseValues;

      // Verify the set of cases we dispatch on.
      for (unsigned i = 0, e = I->getNumCases(); i < e; ++i) {
         PILValue casevalue;
         PILValue result;
         std::tie(casevalue, result) = I->getCase(i);

         if (!isa<PILUndef>(casevalue)) {
            auto  *il = dyn_cast<IntegerLiteralInst>(casevalue);
            require(il,
                    "select_value case operands should refer to integer literals");
            APInt elt = il->getValue();

            require(!seenCaseValues.count(elt),
                    "select_value dispatches on same case value more than once");

            seenCaseValues.insert(elt);
         }

         requireSameType(I->getOperand()->getType(), casevalue->getType(),
                         "select_value case value must match type of operand");

         // The result value must match the type of the instruction.
         requireSameType(result->getType(), I->getType(),
                         "select_value case result must match type of instruction");
      }

      require(I->hasDefault(),
              "select_value should always have a default");
      requireSameType(I->getDefaultResult()->getType(),
                      I->getType(),
                      "select_value default operand must match type of instruction");
   }

   void checkSelectValueInst(SelectValueInst *SVI) {
      require(SVI->getOperand()->getType().isObject(),
              "select_value operand must be an object");

      checkSelectValueCases(SVI);
   }

   void checkSwitchEnumInst(SwitchEnumInst *SOI) {
      require(SOI->getOperand()->getType().isObject(),
              "switch_enum operand must be an object");

      PILType uTy = SOI->getOperand()->getType();
      EnumDecl *uDecl = uTy.getEnumOrBoundGenericEnum();
      require(uDecl, "switch_enum operand is not an enum");

      // Find the set of enum elements for the type so we can verify
      // exhaustiveness.
      llvm::DenseSet<EnumElementDecl*> unswitchedElts;
      uDecl->getAllElements(unswitchedElts);

      // Verify the set of enum cases we dispatch on.
      for (unsigned i = 0, e = SOI->getNumCases(); i < e; ++i) {
         EnumElementDecl *elt;
         PILBasicBlock *dest;
         std::tie(elt, dest) = SOI->getCase(i);

         require(elt->getDeclContext() == uDecl,
                 "switch_enum dispatches on enum element that is not part of "
                 "its type");
         require(unswitchedElts.count(elt),
                 "switch_enum dispatches on same enum element more than once");
         unswitchedElts.erase(elt);

         // The destination BB can take the argument payload, if any, as a BB
         // arguments, or it can ignore it and take no arguments.
         if (elt->hasAssociatedValues()) {
            if (isPILOwnershipEnabled() && F.hasOwnership()) {
               require(dest->getArguments().size() == 1,
                       "switch_enum destination for case w/ args must take 1 "
                       "argument");
            } else {
               require(dest->getArguments().empty() ||
                       dest->getArguments().size() == 1,
                       "switch_enum destination for case w/ args must take 0 or 1 "
                       "arguments");
            }

            if (dest->getArguments().size() == 1) {
               PILType eltArgTy = uTy.getEnumElementType(elt, F.getModule(),
                                                         F.getTypeExpansionContext());
               PILType bbArgTy = dest->getArguments()[0]->getType();
               if (F.getModule().getStage() != PILStage::Lowered) {
                  // During the lowered stage, a function type might have different
                  // signature
                  require(eltArgTy == bbArgTy,
                          "switch_enum destination bbarg must match case arg type");
               }
               require(!dest->getArguments()[0]->getType().isAddress(),
                       "switch_enum destination bbarg type must not be an address");
            }

         } else {
            require(dest->getArguments().empty(),
                    "switch_enum destination for no-argument case must take no "
                    "arguments");
         }
      }

      // If the switch is non-exhaustive, we require a default.
      bool isExhaustive =
         uDecl->isEffectivelyExhaustive(F.getModule().getPolarphpModule(),
                                        F.getResilienceExpansion());
      require((isExhaustive && unswitchedElts.empty()) || SOI->hasDefault(),
              "nonexhaustive switch_enum must have a default destination");
      if (SOI->hasDefault()) {
         // When PIL ownership is enabled, we require all default branches to take
         // an @owned original version of the enum.
         //
         // When PIL ownership is disabled, we no longer support this.
         if (isPILOwnershipEnabled() && F.hasOwnership()) {
            require(SOI->getDefaultBB()->getNumArguments() == 1,
                    "Switch enum default block should have one argument");
            require(SOI->getDefaultBB()->getArgument(0)->getType() ==
                    SOI->getOperand()->getType(),
                    "Switch enum default block should have one argument that is "
                    "the same as the input type");
         } else if (!F.hasOwnership()) {
            require(SOI->getDefaultBB()->args_empty(),
                    "switch_enum default destination must take no arguments");
         }
      }
   }

   void checkSwitchEnumAddrInst(SwitchEnumAddrInst *SOI) {
      require(SOI->getOperand()->getType().isAddress(),
              "switch_enum_addr operand must be an address");

      PILType uTy = SOI->getOperand()->getType();
      EnumDecl *uDecl = uTy.getEnumOrBoundGenericEnum();
      require(uDecl, "switch_enum_addr operand must be an enum");

      // Find the set of enum elements for the type so we can verify
      // exhaustiveness.
      llvm::DenseSet<EnumElementDecl*> unswitchedElts;
      uDecl->getAllElements(unswitchedElts);

      // Verify the set of enum cases we dispatch on.
      for (unsigned i = 0, e = SOI->getNumCases(); i < e; ++i) {
         EnumElementDecl *elt;
         PILBasicBlock *dest;
         std::tie(elt, dest) = SOI->getCase(i);

         require(elt->getDeclContext() == uDecl,
                 "switch_enum_addr dispatches on enum element that "
                 "is not part of its type");
         require(unswitchedElts.count(elt),
                 "switch_enum_addr dispatches on same enum element "
                 "more than once");
         unswitchedElts.erase(elt);

         // The destination BB must not have BB arguments.
         require(dest->getArguments().empty(),
                 "switch_enum_addr destination must take no BB args");
      }

      // If the switch is non-exhaustive, we require a default.
      bool isExhaustive =
         uDecl->isEffectivelyExhaustive(F.getModule().getPolarphpModule(),
                                        F.getResilienceExpansion());
      require((isExhaustive && unswitchedElts.empty()) || SOI->hasDefault(),
              "nonexhaustive switch_enum_addr must have a default destination");

      if (SOI->hasDefault())
         require(SOI->getDefaultBB()->args_empty(),
                 "switch_enum_addr default destination must take "
                 "no arguments");
   }

   bool verifyBranchArgs(PILValue branchArg, PILArgument *bbArg) {
      // NOTE: IRGen currently does not support the following method_inst
      // variants as branch arguments.
      // Once this is supported, the check can be removed.
      require(!(isa<MethodInst>(branchArg) &&
                cast<MethodInst>(branchArg)->getMember().isForeign),
              "branch argument cannot be a witness_method or an objc method_inst");
      require(!(branchArg->getType().is<PILFunctionType>() &&
                branchArg->getType()
                   .castTo<PILFunctionType>()
                   ->getExtInfo()
                   .getRepresentation() ==
                PILFunctionTypeRepresentation::ObjCMethod),
              "branch argument cannot be a objective-c method");
      return branchArg->getType() == bbArg->getType();
   }

   void checkBranchInst(BranchInst *BI) {
      require(BI->getArgs().size() == BI->getDestBB()->args_size(),
              "branch has wrong number of arguments for dest bb");
      require(std::equal(BI->getArgs().begin(), BI->getArgs().end(),
                         BI->getDestBB()->args_begin(),
                         [&](PILValue branchArg, PILArgument *bbArg) {
                            return verifyBranchArgs(branchArg, bbArg);
                         }),
              "branch argument types do not match arguments for dest bb");
   }

   void checkCondBranchInst(CondBranchInst *CBI) {
      // It is important that cond_br keeps an i1 type. ARC Sequence Opts assumes
      // that cond_br does not use reference counted values or decrement reference
      // counted values under the assumption that the instruction that computes
      // the i1 is the use/decrement that ARC cares about and that after that
      // instruction is evaluated, the scalar i1 has a different identity and the
      // object can be deallocated.
      require(CBI->getCondition()->getType() ==
              PILType::getBuiltinIntegerType(1,
                                             CBI->getCondition()->getType().getAstContext()),
              "condition of conditional branch must have Int1 type");

      require(CBI->getTrueArgs().size() == CBI->getTrueBB()->args_size(),
              "true branch has wrong number of arguments for dest bb");
      require(CBI->getTrueBB() != CBI->getFalseBB(),
              "identical destinations");
      require(std::equal(CBI->getTrueArgs().begin(), CBI->getTrueArgs().end(),
                         CBI->getTrueBB()->args_begin(),
                         [&](PILValue branchArg, PILArgument *bbArg) {
                            return verifyBranchArgs(branchArg, bbArg);
                         }),
              "true branch argument types do not match arguments for dest bb");

      require(CBI->getFalseArgs().size() == CBI->getFalseBB()->args_size(),
              "false branch has wrong number of arguments for dest bb");
      require(std::equal(CBI->getFalseArgs().begin(), CBI->getFalseArgs().end(),
                         CBI->getFalseBB()->args_begin(),
                         [&](PILValue branchArg, PILArgument *bbArg) {
                            return verifyBranchArgs(branchArg, bbArg);
                         }),
              "false branch argument types do not match arguments for dest bb");
   }

   void checkDynamicMethodBranchInst(DynamicMethodBranchInst *DMBI) {
      PILType operandType = DMBI->getOperand()->getType();
      // @todo
//      require(DMBI->getMember().getDecl()->isObjC(), "method must be @objc");
      if (!DMBI->getMember().getDecl()->isInstanceMember()) {
         require(operandType.is<MetatypeType>(),
                 "operand must have metatype type");
         require(operandType.castTo<MetatypeType>()
                    ->getInstanceType()->mayHaveSuperclass(),
                 "operand must have metatype of class or class-bound type");
      }

      // Check that the branch argument is of the expected dynamic method type.
      require(DMBI->getHasMethodBB()->args_size() == 1,
              "true bb for dynamic_method_br must take an argument");

      auto bbArgTy = DMBI->getHasMethodBB()->args_begin()[0]->getType();
      require(getDynamicMethodType(operandType, DMBI->getMember())
                 .getAstType()
                 ->isBindableTo(bbArgTy.getAstType()),
              "bb argument for dynamic_method_br must be of the method's type");
   }

   void checkProjectBlockStorageInst(ProjectBlockStorageInst *PBSI) {
      require(PBSI->getOperand()->getType().isAddress(),
              "operand must be an address");
      auto storageTy = PBSI->getOperand()->getType().getAs<PILBlockStorageType>();
      require(storageTy, "operand must be a @block_storage type");

      require(PBSI->getType().isAddress(),
              "result must be an address");
      auto captureTy = PBSI->getType().getAstType();
      require(storageTy->getCaptureType() == captureTy,
              "result must be the capture type of the @block_storage type");
   }

   void checkInitBlockStorageHeaderInst(InitBlockStorageHeaderInst *IBSHI) {
      auto storage = IBSHI->getBlockStorage();
      require(storage->getType().isAddress(),
              "block storage operand must be an address");

      auto storageTy = storage->getType().getAs<PILBlockStorageType>();
      require(storageTy, "block storage operand must be a @block_storage type");

      auto captureTy = storageTy->getCaptureType();
      if (auto capturedFnTy = captureTy->getAs<PILFunctionType>()) {
         if (capturedFnTy->isNoEscape()) {
            // If the capture is a noescape function then it must be possible to
            // locally determine the value stored to initialize the storage for the
            // capture. This is required to diagnose static exclusivity violations
            // when a noescape closure is converted to a noescape block that
            // is then passed to a function.
            auto *storageProjection =
               storage->getSingleUserOfType<ProjectBlockStorageInst>();
            require(storageProjection,
                    "block storage operand with noescape capture must have "
                    "projection from block");

            auto *storeInst = storageProjection->getSingleUserOfType<StoreInst>();
            require(storeInst,
                    "block storage operand with noescape capture must have "
                    "store to projection");
         }
      }

      require(IBSHI->getInvokeFunction()->getType().isObject(),
              "invoke function operand must be a value");
      auto invokeTy
         = IBSHI->getInvokeFunction()->getType().getAs<PILFunctionType>();
      require(invokeTy, "invoke function operand must be a function");
      require(invokeTy->getRepresentation()
              == PILFunctionType::Representation::CFunctionPointer,
              "invoke function operand must be a c function");
      require(invokeTy->getParameters().size() >= 1,
              "invoke function must take at least one parameter");
      require(!invokeTy->getInvocationGenericSignature() ||
              invokeTy->getExtInfo().isPseudogeneric(),
              "invoke function must not take reified generic parameters");

      invokeTy = checkApplySubstitutions(IBSHI->getSubstitutions(),
                                         PILType::getPrimitiveObjectType(invokeTy));

      auto storageParam = invokeTy->getParameters()[0];
      require(storageParam.getConvention() ==
              ParameterConvention::Indirect_InoutAliasable,
              "invoke function must take block storage as @inout_aliasable "
              "parameter");
      require(storageParam.getArgumentType(F.getModule(), invokeTy) == storageTy,
              "invoke function must take block storage type as first parameter");

      require(IBSHI->getType().isObject(), "result must be a value");
      auto blockTy = IBSHI->getType().getAs<PILFunctionType>();
      require(blockTy, "result must be a function");
      require(blockTy->getRepresentation() == PILFunctionType::Representation::Block,
              "result must be a cdecl block function");
      require(blockTy->getResults() == invokeTy->getResults(),
              "result must have same results as invoke function");

      require(blockTy->getParameters().size() + 1
              == invokeTy->getParameters().size(),
              "result must match all parameters of invoke function but the first");
      auto blockParams = blockTy->getParameters();
      auto invokeBlockParams = invokeTy->getParameters().slice(1);
      for (unsigned i : indices(blockParams)) {
         require(blockParams[i] == invokeBlockParams[i],
                 "result must match all parameters of invoke function but the first");
      }
   }

   // @todo
//   void checkObjCInterfaceInst(ObjCInterfaceInst *OPI) {
//      require(OPI->getInterface()->isObjC(),
//              "objc_protocol must be applied to an @objc protocol");
//      auto classTy = OPI->getType();
//      require(classTy.isObject(), "objc_protocol must produce a value");
//      auto classDecl = classTy.getClassOrBoundGenericClass();
//      require(classDecl, "objc_protocol must produce a class instance");
//      require(classDecl->getName() == F.getAstContext().Id_Interface,
//              "objc_protocol must produce an instance of ObjectiveC.Interface class");
//      require(classDecl->getModuleContext()->getName() == F.getAstContext().Id_ObjectiveC,
//              "objc_protocol must produce an instance of ObjectiveC.Interface class");
//   }
//
//   void checkObjCMetatypeToObjectInst(ObjCMetatypeToObjectInst *OMOI) {
//      require(OMOI->getOperand()->getType().isObject(),
//              "objc_metatype_to_object must take a value");
//      auto fromMetaTy = OMOI->getOperand()->getType().getAs<MetatypeType>();
//      require(fromMetaTy, "objc_metatype_to_object must take an @objc metatype value");
//      require(fromMetaTy->getRepresentation() == MetatypeRepresentation::ObjC,
//              "objc_metatype_to_object must take an @objc metatype value");
//      require(OMOI->getType().isObject(),
//              "objc_metatype_to_object must produce a value");
//      require(OMOI->getType().getAstType()->isAnyObject(),
//              "objc_metatype_to_object must produce an AnyObject value");
//   }
//
//   void checkObjCExistentialMetatypeToObjectInst(
//      ObjCExistentialMetatypeToObjectInst *OMOI) {
//      require(OMOI->getOperand()->getType().isObject(),
//              "objc_metatype_to_object must take a value");
//      auto fromMetaTy = OMOI->getOperand()->getType()
//         .getAs<ExistentialMetatypeType>();
//      require(fromMetaTy, "objc_metatype_to_object must take an @objc existential metatype value");
//      require(fromMetaTy->getRepresentation() == MetatypeRepresentation::ObjC,
//              "objc_metatype_to_object must take an @objc existential metatype value");
//      require(OMOI->getType().isObject(),
//              "objc_metatype_to_object must produce a value");
//      require(OMOI->getType().getAstType()->isAnyObject(),
//              "objc_metatype_to_object must produce an AnyObject value");
//   }

   void checkKeyPathInst(KeyPathInst *KPI) {
      auto kpTy = KPI->getType();

      require(kpTy.isObject(), "keypath result must be an object type");

      auto kpBGT = kpTy.getAs<BoundGenericType>();
      require(kpBGT, "keypath result must be a generic type");
      auto &C = F.getAstContext();
      require(kpBGT->getDecl() == C.getKeyPathDecl()
              || kpBGT->getDecl() == C.getWritableKeyPathDecl()
              || kpBGT->getDecl() == C.getReferenceWritableKeyPathDecl(),
              "keypath result must be a key path type");

      auto baseTy = CanType(kpBGT->getGenericArgs()[0]);
      auto pattern = KPI->getPattern();
      SubstitutionMap patternSubs = KPI->getSubstitutions();
      require(baseTy == pattern->getRootType().subst(patternSubs)->getCanonicalType(),
              "keypath root type should match root type of keypath pattern");

      auto leafTy = CanType(kpBGT->getGenericArgs()[1]);
      require(leafTy == pattern->getValueType().subst(patternSubs)->getCanonicalType(),
              "keypath value type should match value type of keypath pattern");

      {
         for (auto &component : pattern->getComponents()) {
            bool hasIndices;
            switch (component.getKind()) {
               case KeyPathPatternComponent::Kind::GettableProperty:
               case KeyPathPatternComponent::Kind::SettableProperty:
                  hasIndices = !component.getSubscriptIndices().empty();
                  break;

               case KeyPathPatternComponent::Kind::StoredProperty:
               case KeyPathPatternComponent::Kind::OptionalChain:
               case KeyPathPatternComponent::Kind::OptionalWrap:
               case KeyPathPatternComponent::Kind::OptionalForce:
               case KeyPathPatternComponent::Kind::TupleElement:
                  hasIndices = false;
                  break;
            }

            verifyKeyPathComponent(F.getModule(), F.getResilienceExpansion(),
                                   [&](bool reqt, StringRef message) { _require(reqt, message); },
                                   baseTy,
                                   leafTy,
                                   component,
                                   KPI->getAllOperands(),
                                   KPI->getPattern()->getGenericSignature(),
                                   KPI->getSubstitutions(),
               /*property descriptor*/false,
                                   hasIndices);
         }
      }
      require(CanType(baseTy) == CanType(leafTy),
              "final component should match leaf value type of key path type");
   }

   void checkIsEscapingClosureInst(IsEscapingClosureInst *IEC) {
      // The closure operand is allowed to be an optional closure.
      auto operandType = IEC->getOperand()->getType();
      if (operandType.getOptionalObjectType())
         operandType = operandType.getOptionalObjectType();

      auto fnType = operandType.getAs<PILFunctionType>();
      require(fnType && fnType->getExtInfo().hasContext() &&
              !fnType->isNoEscape() &&
              fnType->getExtInfo().getRepresentation() ==
              PILFunctionTypeRepresentation::Thick,
              "is_escaping_closure must have a thick "
              "function operand");
      require(IEC->getVerificationType() == IsEscapingClosureInst::ObjCEscaping ||
              IEC->getVerificationType() ==
              IsEscapingClosureInst::WithoutActuallyEscaping,
              "unknown verfication type");
   }

   // This verifies that the entry block of a PIL function doesn't have
   // any predecessors and also verifies the entry point arguments.
   void verifyEntryBlock(PILBasicBlock *entry) {
      require(entry->pred_empty(), "entry block cannot have predecessors");

      LLVM_DEBUG(llvm::dbgs() << "Argument types for entry point BB:\n";
                    for (auto *arg
                       : make_range(entry->args_begin(), entry->args_end()))
                       arg->getType()
                          .dump();
                    llvm::dbgs() << "Input types for PIL function type ";
                    F.getLoweredFunctionType()->print(llvm::dbgs());
                    llvm::dbgs() << ":\n";
                    for (auto paramTy
                       : fnConv.getParameterPILTypes()) { paramTy.dump(); });

      require(entry->args_size() == (fnConv.getNumIndirectPILResults()
                                     + fnConv.getNumParameters()),
              "entry point has wrong number of arguments");

      bool matched = true;
      auto argI = entry->args_begin();

      auto check = [&](const char *what, PILType ty) {
         auto mappedTy = F.mapTypeIntoContext(ty);
         PILArgument *bbarg = *argI;
         ++argI;
         if (bbarg->getType() != mappedTy &&
             bbarg->getType() != F.getLoweredType(mappedTy.getAstType())
                .getCategoryType(mappedTy.getCategory())) {
            llvm::errs() << what << " type mismatch!\n";
            llvm::errs() << "  argument: "; bbarg->dump();
            llvm::errs() << "  expected: "; mappedTy.dump();
            matched = false;
         }

         // If we do not have qualified ownership, do not check ownership.
         if (!F.hasOwnership()) {
            return;
         }

         auto ownershipkind = ValueOwnershipKind(
            F, mappedTy, fnConv.getPILArgumentConvention(bbarg->getIndex()));

         if (bbarg->getOwnershipKind() != ownershipkind) {
            llvm::errs() << what << " ownership kind mismatch!\n";
            llvm::errs() << "  argument: " << bbarg->getOwnershipKind() << '\n';
            llvm::errs() << "  expected: " << ownershipkind << '\n';
            matched = false;
         }
      };

      for (auto result : fnConv.getIndirectPILResults()) {
         assert(fnConv.isPILIndirect(result));
         check("result", fnConv.getPILType(result));
      }
      for (auto param : F.getLoweredFunctionType()->getParameters()) {
         check("parameter", fnConv.getPILType(param));
      }

      require(matched, "entry point argument types do not match function type");

      // TBAA requirement for all address arguments.
      require(std::equal(entry->args_begin() + fnConv.getNumIndirectPILResults(),
                         entry->args_end(),
                         fnConv.funcTy->getParameters().begin(),
                         [&](PILArgument *bbarg, PILParameterInfo paramInfo) {
                            if (!bbarg->getType().isAddress())
                               return true;
                            switch (paramInfo.getConvention()) {
                               default:
                                  return false;
                               case ParameterConvention::Indirect_In:
                               case ParameterConvention::Indirect_In_Constant:
                               case ParameterConvention::Indirect_Inout:
                               case ParameterConvention::Indirect_InoutAliasable:
                               case ParameterConvention::Indirect_In_Guaranteed:
                                  return true;
                            }
                         }),
              "entry point address argument must have an indirect calling "
              "convention");
   }

   void verifyEpilogBlocks(PILFunction *F) {
      bool FoundReturnBlock = false;
      bool FoundThrowBlock = false;
      bool FoundUnwindBlock = false;
      for (auto &BB : *F) {
         if (isa<ReturnInst>(BB.getTerminator())) {
            require(!FoundReturnBlock,
                    "more than one return block in function");
            FoundReturnBlock = true;
         } else if (isa<ThrowInst>(BB.getTerminator())) {
            require(!FoundThrowBlock,
                    "more than one throw block in function");
            FoundThrowBlock = true;
         } else if (isa<UnwindInst>(BB.getTerminator())) {
            require(!FoundUnwindBlock,
                    "more than one unwind block in function");
            FoundUnwindBlock = true;
         } else {
            assert(!BB.getTerminator()->isFunctionExiting());
         }
      }
   }

   bool isUnreachableAlongAllPathsStartingAt(
      PILBasicBlock *StartBlock, SmallPtrSetImpl<PILBasicBlock *> &Visited) {
      if (isa<UnreachableInst>(StartBlock->getTerminator()))
         return true;
      else if (isa<ReturnInst>(StartBlock->getTerminator()))
         return false;
      else if (isa<ThrowInst>(StartBlock->getTerminator()))
         return false;

      // Recursively check all successors.
      for (auto *SuccBB : StartBlock->getSuccessorBlocks())
         if (!Visited.insert(SuccBB).second)
            if (!isUnreachableAlongAllPathsStartingAt(SuccBB, Visited))
               return false;

      return true;
   }

   void verifyPILFunctionType(CanPILFunctionType FTy) {
      // Make sure that if FTy's calling convention implies that it must have a
      // self parameter.
      require(!FTy->hasSelfParam() || !FTy->getParameters().empty(),
              "Functions with a calling convention with self parameter must "
              "have at least one argument for self.");
   }

   struct VerifyFlowSensitiveRulesDetails {
      enum CFGState {
         /// No special rules are in play.
            Normal,
         /// We've followed the resume edge of a yield in a yield_once coroutine.
            YieldOnceResume,
         /// We've followed the unwind edge of a yield.
            YieldUnwind
      };

      struct BBState {
         std::vector<SingleValueInstruction*> Stack;

         /// Contents: BeginAccessInst*, BeginApplyInst*.
         std::set<PILInstruction*> ActiveOps;

         CFGState CFG = Normal;
      };
   };

   /// Verify the various control-flow-sensitive rules of PIL:
   ///
   /// - stack allocations and deallocations must obey a stack discipline
   /// - accesses must be uniquely ended
   /// - flow-sensitive states must be equivalent on all paths into a block
   void verifyFlowSensitiveRules(PILFunction *F) {
      // Do a traversal of the basic blocks.
      // Note that we intentionally don't verify these properties in blocks
      // that can't be reached from the entry block.
      llvm::DenseMap<PILBasicBlock*, VerifyFlowSensitiveRulesDetails::BBState> visitedBBs;
      SmallVector<PILBasicBlock*, 16> Worklist;
      visitedBBs.try_emplace(&*F->begin());
      Worklist.push_back(&*F->begin());
      while (!Worklist.empty()) {
         PILBasicBlock *BB = Worklist.pop_back_val();
         VerifyFlowSensitiveRulesDetails::BBState state = visitedBBs[BB];
         for (PILInstruction &i : *BB) {
            CurInstruction = &i;

            if (i.isAllocatingStack()) {
               state.Stack.push_back(cast<SingleValueInstruction>(&i));

            } else if (i.isDeallocatingStack()) {
               PILValue op = i.getOperand(0);
               require(!state.Stack.empty(),
                       "stack dealloc with empty stack");
               require(op == state.Stack.back(),
                       "stack dealloc does not match most recent stack alloc");
               state.Stack.pop_back();

            } else if (isa<BeginAccessInst>(i) || isa<BeginApplyInst>(i)) {
               bool notAlreadyPresent = state.ActiveOps.insert(&i).second;
               require(notAlreadyPresent,
                       "operation was not ended before re-beginning it");

            } else if (isa<EndAccessInst>(i) || isa<AbortApplyInst>(i) ||
                       isa<EndApplyInst>(i)) {
               if (auto beginOp = i.getOperand(0)->getDefiningInstruction()) {
                  bool present = state.ActiveOps.erase(beginOp);
                  require(present, "operation has already been ended");
               }

            } else if (auto term = dyn_cast<TermInst>(&i)) {
               if (term->isFunctionExiting()) {
                  require(state.Stack.empty(),
                          "return with stack allocs that haven't been deallocated");
                  require(state.ActiveOps.empty(),
                          "return with operations still active");

                  if (isa<UnwindInst>(term)) {
                     require(state.CFG == VerifyFlowSensitiveRulesDetails::YieldUnwind,
                             "encountered 'unwind' when not on unwind path");
                  } else {
                     require(state.CFG != VerifyFlowSensitiveRulesDetails::YieldUnwind,
                             "encountered 'return' or 'throw' when on unwind path");
                     if (isa<ReturnInst>(term) &&
                         F->getLoweredFunctionType()->getCoroutineKind() ==
                         PILCoroutineKind::YieldOnce &&
                         F->getModule().getStage() != PILStage::Raw) {
                        require(state.CFG == VerifyFlowSensitiveRulesDetails::YieldOnceResume,
                                "encountered 'return' before yielding a value in "
                                "yield_once coroutine");
                     }
                  }
               }

               if (isa<YieldInst>(term)) {
                  require(state.CFG != VerifyFlowSensitiveRulesDetails::YieldOnceResume,
                          "encountered multiple 'yield's along single path");
                  require(state.CFG == VerifyFlowSensitiveRulesDetails::Normal,
                          "encountered 'yield' on abnormal CFG path");
               }

               auto successors = term->getSuccessors();
               for (auto i : indices(successors)) {
                  PILBasicBlock *succBB = successors[i].getBB();

                  // Optimistically try to set our current state as the state
                  // of the successor.  We can use a move on the final successor;
                  // note that if the insertion fails, the move won't actually
                  // happen, which is important because we'll still need it
                  // to compare against the already-recorded state for the block.
                  auto insertResult =
                     i + 1 == successors.size()
                     ? visitedBBs.try_emplace(succBB, std::move(state))
                     : visitedBBs.try_emplace(succBB, state);

                  // If the insertion was successful, add the successor to the
                  // worklist and continue.
                  if (insertResult.second) {
                     Worklist.push_back(succBB);

                     // If we're following a 'yield', update the CFG state:
                     if (isa<YieldInst>(term)) {
                        // Enforce that the unwind logic is segregated in all stages.
                        if (i == 1) {
                           insertResult.first->second.CFG = VerifyFlowSensitiveRulesDetails::YieldUnwind;

                           // We check the yield_once rule in the mandatory analyses,
                           // so we can't assert it yet in the raw stage.
                        } else if (F->getLoweredFunctionType()->getCoroutineKind()
                                   == PILCoroutineKind::YieldOnce &&
                                   F->getModule().getStage() != PILStage::Raw) {
                           insertResult.first->second.CFG = VerifyFlowSensitiveRulesDetails::YieldOnceResume;
                        }
                     }

                     continue;
                  }

                  // This rule is checked elsewhere, but we'd want to assert it
                  // here anyway.
                  require(!isa<YieldInst>(term),
                          "successor of 'yield' should not be encountered twice");

                  // Check that the stack height is consistent coming from all entry
                  // points into this BB. We only care about consistency if there is
                  // a possible return from this function along the path starting at
                  // this successor bb.  (FIXME: Why? Infinite loops should still
                  // preserve consistency...)
                  auto isUnreachable = [&] {
                     SmallPtrSet<PILBasicBlock *, 16> visited;
                     return isUnreachableAlongAllPathsStartingAt(succBB, visited);
                  };

                  const auto &foundState = insertResult.first->second;
                  require(state.Stack == foundState.Stack || isUnreachable(),
                          "inconsistent stack heights entering basic block");
                  require(state.ActiveOps == foundState.ActiveOps || isUnreachable(),
                          "inconsistent active-operations sets entering basic block");
                  require(state.CFG == foundState.CFG,
                          "inconsistent coroutine states entering basic block");
               }
            }
         }
      }
   }

   void verifyBranches(const PILFunction *F) {
      // Verify that there is no non_condbr critical edge.
      auto isCriticalEdgePred = [](const TermInst *T, unsigned EdgeIdx) {
         assert(T->getSuccessors().size() > EdgeIdx && "Not enough successors");

         // A critical edge has more than one outgoing edges from the source
         // block.
         auto SrcSuccs = T->getSuccessors();
         if (SrcSuccs.size() <= 1)
            return false;

         // And its destination block has more than one predecessor.
         PILBasicBlock *DestBB = SrcSuccs[EdgeIdx];
         assert(!DestBB->pred_empty() && "There should be a predecessor");
         if (DestBB->getSinglePredecessorBlock())
            return false;

         return true;
      };

      for (auto &BB : *F) {
         const TermInst *TI = BB.getTerminator();
         CurInstruction = TI;

         // Check for non-cond_br critical edges.
         auto *CBI = dyn_cast<CondBranchInst>(TI);
         if (!CBI) {
            for (unsigned Idx = 0, e = BB.getSuccessors().size(); Idx != e; ++Idx) {
               require(!isCriticalEdgePred(TI, Idx),
                       "non cond_br critical edges not allowed");
            }
            continue;
         }
         // In ownership qualified PIL, ban critical edges from CondBranchInst that
         // have non-trivial arguments.
         //
         // FIXME: it would be far simpler to ban all critical edges in general.
         if (!F->hasOwnership())
            continue;

         if (isCriticalEdgePred(CBI, CondBranchInst::TrueIdx)) {
            require(
               llvm::all_of(CBI->getTrueArgs(),
                            [](PILValue V) -> bool {
                               return V.getOwnershipKind() ==
                                      ValueOwnershipKind::None;
                            }),
               "cond_br with critical edges must not have a non-trivial value");
         }
         if (isCriticalEdgePred(CBI, CondBranchInst::FalseIdx)) {
            require(
               llvm::all_of(CBI->getFalseArgs(),
                            [](PILValue V) -> bool {
                               return V.getOwnershipKind() ==
                                      ValueOwnershipKind::None;
                            }),
               "cond_br with critical edges must not have a non-trivial value");
         }
      }
   }

   void verifyOpenedArchetypes(PILFunction *F) {
      require(OpenedArchetypes.getFunction() == F,
              "Wrong PILFunction provided to verifyOpenedArchetypes");
      // Check that definitions of all opened archetypes from
      // OpenedArchetypesDefs are existing instructions
      // belonging to the function F.
      for (auto KV: OpenedArchetypes.getOpenedArchetypeDefs()) {
         require(getOpenedArchetypeOf(CanType(KV.first)),
                 "Only opened archetypes should be registered in PILFunction");
         auto Def = cast<PILInstruction>(KV.second);
         require(Def->getFunction() == F,
                 "Definition of every registered opened archetype should be an"
                 " existing instruction in a current PILFunction");
      }
   }

   /// This pass verifies that there are no hole in debug scopes at -Onone.
   void verifyDebugScopeHoles(PILBasicBlock *BB) {
      if (!VerifyDIHoles)
         return;

      // This check only makes sense at -Onone. Optimizations,
      // e.g. inlining, can move scopes around.
      llvm::DenseSet<const PILDebugScope *> AlreadySeenScopes;
      if (BB->getParent()->getEffectiveOptimizationMode() !=
          OptimizationMode::NoOptimization)
         return;

      // Exit early if this BB is empty.
      if (BB->empty())
         return;

      const PILDebugScope *LastSeenScope = nullptr;
      for (PILInstruction &SI : *BB) {
         if (SI.isMetaInstruction())
            continue;
         LastSeenScope = SI.getDebugScope();
         AlreadySeenScopes.insert(LastSeenScope);
         break;
      }
      for (PILInstruction &SI : *BB) {
         if (SI.isMetaInstruction())
            continue;

         // If we haven't seen this debug scope yet, update the
         // map and go on.
         auto *DS = SI.getDebugScope();
         assert(DS && "Each instruction should have a debug scope");
         if (!AlreadySeenScopes.count(DS)) {
            AlreadySeenScopes.insert(DS);
            LastSeenScope = DS;
            continue;
         }

         // Otherwise, we're allowed to re-enter a scope only if
         // the scope is an ancestor of the scope we're currently leaving.
         auto isAncestorScope = [](const PILDebugScope *Cur,
                                   const PILDebugScope *Previous) {
            const PILDebugScope *Tmp = Previous;
            assert(Tmp && "scope can't be null");
            while (Tmp) {
               PointerUnion<const PILDebugScope *, PILFunction *> Parent =
                  Tmp->Parent;
               auto *ParentScope = Parent.dyn_cast<const PILDebugScope *>();
               if (!ParentScope)
                  break;
               if (ParentScope == Cur)
                  return true;
               Tmp = ParentScope;
            }
            return false;
         };

         if (isAncestorScope(DS, LastSeenScope)) {
            LastSeenScope = DS;
            continue;
         }
         if (DS != LastSeenScope) {
            LLVM_DEBUG(llvm::dbgs() << "Broken instruction!\n"; SI.dump());
            LLVM_DEBUG(llvm::dbgs() << "Please report a bug on bugs.swift.org\n");
            LLVM_DEBUG(llvm::dbgs() <<
                                    "Pass -Xllvm -verify-di-holes=false to disable the verification\n");
            require(
               DS == LastSeenScope,
               "Basic block contains a non-contiguous lexical scope at -Onone");
         }
      }
   }

   void visitPILBasicBlock(PILBasicBlock *BB) {
      // Make sure that each of the successors/predecessors of this basic block
      // have this basic block in its predecessor/successor list.
      for (const auto *SuccBB : BB->getSuccessorBlocks()) {
         require(SuccBB->isPredecessorBlock(BB),
                 "Must be a predecessor of each successor.");
      }

      for (const PILBasicBlock *PredBB : BB->getPredecessorBlocks()) {
         require(PredBB->isSuccessorBlock(BB),
                 "Must be a successor of each predecessor.");
      }

      PILInstructionVisitor::visitPILBasicBlock(BB);
      verifyDebugScopeHoles(BB);
   }

   void visitBasicBlockArguments(PILBasicBlock *BB) {
      CurInstruction = nullptr;
      for (auto argI = BB->args_begin(), argEnd = BB->args_end(); argI != argEnd;
           ++argI)
         visitPILArgument(*argI);
   }

   void visitPILBasicBlocks(PILFunction *F) {
      // Visit all basic blocks in the RPOT order.
      // This ensures that any open_existential instructions, which
      // open archetypes, are seen before the uses of these archetypes.
      llvm::ReversePostOrderTraversal<PILFunction *> RPOT(F);
      llvm::DenseSet<PILBasicBlock *> VisitedBBs;
      for (auto Iter = RPOT.begin(), E = RPOT.end(); Iter != E; ++Iter) {
         auto *BB = *Iter;
         VisitedBBs.insert(BB);
         visitPILBasicBlock(BB);
      }

      // Visit all basic blocks that were not visited during the RPOT traversal,
      // e.g. unreachable basic blocks.
      for (auto &BB : *F) {
         if (VisitedBBs.count(&BB))
            continue;
         visitPILBasicBlock(&BB);
      }
   }

   void visitPILFunction(PILFunction *F) {
      PrettyStackTracePILFunction stackTrace("verifying", F);

      CanPILFunctionType FTy = F->getLoweredFunctionType();
      verifyPILFunctionType(FTy);

      if (F->isExternalDeclaration()) {
         if (F->hasForeignBody())
            return;

         require(F->isAvailableExternally(),
                 "external declaration of internal PILFunction not allowed");
         // If F is an external declaration, there is nothing further to do,
         // return.
         return;
      }

      assert(!F->hasForeignBody());

      // Make sure that our PILFunction only has context generic params if our
      // PILFunctionType is non-polymorphic.
      if (F->getGenericEnvironment()) {
         require(FTy->isPolymorphic(),
                 "non-generic function definitions cannot have a "
                 "generic environment");
      } else {
         require(!FTy->isPolymorphic(),
                 "generic function definition must have a generic environment");
      }

      // Otherwise, verify the body of the function.
      verifyEntryBlock(&*F->getBlocks().begin());
      verifyEpilogBlocks(F);
      verifyFlowSensitiveRules(F);
      verifyBranches(F);

      visitPILBasicBlocks(F);

      // Verify archetypes after all basic blocks are visited,
      // because we build the map of archetypes as we visit the
      // instructions.
      verifyOpenedArchetypes(F);

      if (F->hasOwnership() && F->shouldVerifyOwnership() &&
          !F->getModule().getAstContext().hadError()) {
         verifyMemoryLifetime(F);
      }
   }

   void verify() {
      visitPILFunction(const_cast<PILFunction*>(&F));
   }
};
} // end anonymous namespace

#undef require
#undef requireObjectType

//===----------------------------------------------------------------------===//
//                     Out of Line Verifier Run Functions
//===----------------------------------------------------------------------===//

/// verify - Run the PIL verifier to make sure that the PILFunction follows
/// invariants.
void PILFunction::verify(bool SingleFunction) const {
#ifdef NDEBUG
   if (!getModule().getOptions().VerifyAll)
    return;
#endif
   // Please put all checks in visitPILFunction in PILVerifier, not here. This
   // ensures that the pretty stack trace in the verifier is included with the
   // back trace when the verifier crashes.
   PILVerifier(*this, SingleFunction).verify();
}

void PILFunction::verifyCriticalEdges() const {
#ifdef NDEBUG
   if (!getModule().getOptions().VerifyAll)
    return;
#endif
   PILVerifier(*this, /*SingleFunction=*/true).verifyBranches(this);
}

/// Verify that a property descriptor follows invariants.
void PILProperty::verify(const PILModule &M) const {
#ifdef NDEBUG
   if (!M.getOptions().VerifyAll)
    return;
#endif

   auto *decl = getDecl();
   auto *dc = decl->getInnermostDeclContext();

   // TODO: base type for global/static descriptors
   auto sig = dc->getGenericSignatureOfContext();
   auto baseTy = dc->getInnermostTypeContext()->getSelfInterfaceType()
      ->getCanonicalType(sig);
   auto leafTy = decl->getValueInterfaceType()->getCanonicalType(sig);
   SubstitutionMap subs;
   if (sig) {
      auto env = dc->getGenericEnvironmentOfContext();
      subs = env->getForwardingSubstitutionMap();
      baseTy = env->mapTypeIntoContext(baseTy)->getCanonicalType();
      leafTy = env->mapTypeIntoContext(leafTy)->getCanonicalType();
   }
   bool hasIndices = false;
   if (auto subscript = dyn_cast<SubscriptDecl>(decl)) {
      hasIndices = subscript->getIndices()->size() != 0;
   }

   auto canSig = sig ? sig->getCanonicalSignature() : nullptr;

   auto require = [&](bool reqt, StringRef message) {
      if (!reqt) {
         llvm::errs() << message << "\n";
         assert(false && "invoking standard assertion failure");
      }
   };

   if (auto &component = getComponent()) {
      verifyKeyPathComponent(const_cast<PILModule&>(M),
                             ResilienceExpansion::Maximal,
                             require,
                             baseTy,
                             leafTy,
                             *component,
                             {},
                             canSig,
                             subs,
         /*property descriptor*/true,
                             hasIndices);
      // verifyKeyPathComponent updates baseTy to be the projected type of the
      // component, which should be the same as the type of the declared storage
      require(baseTy == leafTy,
              "component type of property descriptor should match type of storage");
   }
}

/// Verify that a vtable follows invariants.
void PILVTable::verify(const PILModule &M) const {
#ifdef NDEBUG
   if (!M.getOptions().VerifyAll)
    return;
#endif
   for (auto &entry : getEntries()) {
      // All vtable entries must be decls in a class context.
      assert(entry.Method.hasDecl() && "vtable entry is not a decl");
      auto baseInfo =
         M.Types.getConstantInfo(TypeExpansionContext::minimal(), entry.Method);
      ValueDecl *decl = entry.Method.getDecl();

      assert((!isa<AccessorDecl>(decl)
              || !cast<AccessorDecl>(decl)->isObservingAccessor())
             && "observing accessors shouldn't have vtable entries");

      // For ivar destroyers, the decl is the class itself.
      ClassDecl *theClass;
      if (entry.Method.kind == PILDeclRef::Kind::IVarDestroyer)
         theClass = dyn_cast<ClassDecl>(decl);
      else
         theClass = dyn_cast<ClassDecl>(decl->getDeclContext());

      assert(theClass && "vtable entry must refer to a class member");

      // The class context must be the vtable's class, or a superclass thereof.
      assert(theClass->isSuperclassOf(getClass()) &&
             "vtable entry must refer to a member of the vtable's class");

      // All function vtable entries must be at their natural uncurry level.
      assert(!entry.Method.isCurried && "vtable entry must not be curried");

      // Foreign entry points shouldn't appear in vtables.
      assert(!entry.Method.isForeign && "vtable entry must not be foreign");

      // The vtable entry must be ABI-compatible with the overridden vtable slot.
      SmallString<32> baseName;
      {
         llvm::raw_svector_ostream os(baseName);
         entry.Method.print(os);
      }

      if (M.getStage() != PILStage::Lowered) {
         PILVerifier(*entry.Implementation)
            .requireABICompatibleFunctionTypes(
               baseInfo.getPILType().castTo<PILFunctionType>(),
               entry.Implementation->getLoweredFunctionType(),
               "vtable entry for " + baseName + " must be ABI-compatible",
               *entry.Implementation);
      }
   }
}

/// Verify that a witness table follows invariants.
void PILWitnessTable::verify(const PILModule &M) const {
#ifdef NDEBUG
   if (!M.getOptions().VerifyAll)
    return;
#endif
   if (isDeclaration())
      assert(getEntries().empty() &&
             "A witness table declaration should not have any entries.");

   for (const Entry &E : getEntries())
      if (E.getKind() == PILWitnessTable::WitnessKind::Method) {
         PILFunction *F = E.getMethodWitness().Witness;
         if (F) {
            // If a PILWitnessTable is going to be serialized, it must only
            // reference public or serializable functions.
            if (isSerialized()) {
               assert(F->hasValidLinkageForFragileRef() &&
                      "Fragile witness tables should not reference "
                      "less visible functions.");
            }

            assert(F->getLoweredFunctionType()->getRepresentation() ==
                   PILFunctionTypeRepresentation::WitnessMethod &&
                   "Witnesses must have witness_method representation.");
         }
      }
}

/// Verify that a default witness table follows invariants.
void PILDefaultWitnessTable::verify(const PILModule &M) const {
#ifndef NDEBUG
   for (const Entry &E : getEntries()) {
      // FIXME: associated type witnesses.
      if (!E.isValid() || E.getKind() != PILWitnessTable::Method)
         continue;

      PILFunction *F = E.getMethodWitness().Witness;

#if 0
      // FIXME: For now, all default witnesses are private.
    assert(F->hasValidLinkageForFragileRef() &&
           "Default witness tables should not reference "
           "less visible functions.");
#endif

      assert(F->getLoweredFunctionType()->getRepresentation() ==
             PILFunctionTypeRepresentation::WitnessMethod &&
             "Default witnesses must have witness_method representation.");
   }
#endif
}

/// Verify that a global variable follows invariants.
void PILGlobalVariable::verify() const {
#ifdef NDEBUG
   if (!getModule().getOptions().VerifyAll)
    return;
#endif
   assert(getLoweredType().isObject()
          && "global variable cannot have address type");

   // Verify the static initializer.
   for (const PILInstruction &I : StaticInitializerBlock) {
      assert(isValidStaticInitializerInst(&I, getModule()) &&
             "illegal static initializer");
      auto init = cast<SingleValueInstruction>(&I);
      if (init == &StaticInitializerBlock.back()) {
         assert(init->use_empty() && "Init value must not have another use");
      } else {
         assert(!init->use_empty() && "dead instruction in static initializer");
         assert(!isa<ObjectInst>(init) &&
                "object instruction is only allowed for final initial value");
      }
      assert(I.getParent() == &StaticInitializerBlock);
   }
}

/// Verify the module.
void PILModule::verify() const {
#ifdef NDEBUG
   if (!getOptions().VerifyAll)
    return;
#endif
   // Uniquing set to catch symbol name collisions.
   llvm::DenseSet<StringRef> symbolNames;

   // When merging partial modules, we only link functions from the current
   // module, without enabling "LinkAll" mode or running the PILLinker pass;
   // in this case, we need to relax some of the checks.
   bool SingleFunction = false;
   if (getOptions().MergePartialModules)
      SingleFunction = true;

   // Check all functions.
   for (const PILFunction &f : *this) {
      if (!symbolNames.insert(f.getName()).second) {
         llvm::errs() << "Symbol redefined: " << f.getName() << "!\n";
         assert(false && "triggering standard assertion failure routine");
      }
      f.verify(SingleFunction);
   }

   // Check all globals.
   for (const PILGlobalVariable &g : getPILGlobals()) {
      if (!symbolNames.insert(g.getName()).second) {
         llvm::errs() << "Symbol redefined: " << g.getName() << "!\n";
         assert(false && "triggering standard assertion failure routine");
      }
      g.verify();
   }

   // Check all vtables and the vtable cache.
   llvm::DenseSet<ClassDecl*> vtableClasses;
   unsigned EntriesSZ = 0;
   for (const PILVTable &vt : getVTables()) {
      if (!vtableClasses.insert(vt.getClass()).second) {
         llvm::errs() << "Vtable redefined: " << vt.getClass()->getName() << "!\n";
         assert(false && "triggering standard assertion failure routine");
      }
      vt.verify(*this);
      // Check if there is a cache entry for each vtable entry
      for (auto entry : vt.getEntries()) {
         if (VTableEntryCache.find({&vt, entry.Method}) == VTableEntryCache.end()) {
            llvm::errs() << "Vtable entry for function: "
                         << entry.Implementation->getName() << "not in cache!\n";
            assert(false && "triggering standard assertion failure routine");
         }
         EntriesSZ++;
      }
   }
   assert(EntriesSZ == VTableEntryCache.size() &&
          "Cache size is not equal to true number of VTable entries");

   // Check all witness tables.
   LLVM_DEBUG(llvm::dbgs() <<"*** Checking witness tables for duplicates ***\n");
   llvm::DenseSet<RootInterfaceConformance*> wtableConformances;
   for (const PILWitnessTable &wt : getWitnessTables()) {
      LLVM_DEBUG(llvm::dbgs() << "Witness Table:\n"; wt.dump());
      auto conformance = wt.getConformance();
      if (!wtableConformances.insert(conformance).second) {
         llvm::errs() << "Witness table redefined: ";
         conformance->printName(llvm::errs());
         assert(false && "triggering standard assertion failure routine");
      }
      wt.verify(*this);
   }

   // Check all default witness tables.
   LLVM_DEBUG(llvm::dbgs() << "*** Checking default witness tables for "
                              "duplicates ***\n");
   llvm::DenseSet<const InterfaceDecl *> defaultWitnessTables;
   for (const PILDefaultWitnessTable &wt : getDefaultWitnessTables()) {
      LLVM_DEBUG(llvm::dbgs() << "Default Witness Table:\n"; wt.dump());
      if (!defaultWitnessTables.insert(wt.getInterface()).second) {
         llvm::errs() << "Default witness table redefined: ";
         wt.dump();
         assert(false && "triggering standard assertion failure routine");
      }
      wt.verify(*this);
   }

   // Check property descriptors.
   LLVM_DEBUG(llvm::dbgs() << "*** Checking property descriptors ***\n");
   for (auto &prop : getPropertyList()) {
      prop.verify(*this);
   }
}

/// Determine whether an instruction may not have a PILDebugScope.
bool polar::maybeScopeless(PILInstruction &I) {
   if (I.getFunction()->isBare())
      return true;
   return !isa<DebugValueInst>(I) && !isa<DebugValueAddrInst>(I);
}
